Quotient graphs and stochastic matrices

Whenever graphs admit equitable partitions, their quotient graphs highlight the structure evidenced by the partition. It is therefore very natural to ask what can be said about two graphs that have the same quotient according to certain equitable partitions. This question has been connected to the t...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-11
Main Authors: Cançado, Frederico, Coutinho, Gabriel
Format: Article
Language:English
Subjects:
Apexes
Combinatorial analysis
Graphs
Isomorphism
Quotients
Structural analysis
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Whenever graphs admit equitable partitions, their quotient graphs highlight the structure evidenced by the partition. It is therefore very natural to ask what can be said about two graphs that have the same quotient according to certain equitable partitions. This question has been connected to the theory of fractional isomorphisms and covers of graphs in well-known results that we briefly survey in this paper. We then depart to develop theory of what happens when the two graphs have the same symmetrized quotient, proving a structural result connecting this with the existence of certain doubly stochastic matrices. We apply this theorem to derive a new characterization of when two graphs have the same combinatorial quotient, and we also study graphs with weighted vertices and the related concept of pseudo-equitable partitions. Our results connect to known old and recent results, and are naturally applicable to study quantum walks.
ISSN:2331-8422