Compact graphs and equitable partitions

✍ Scribed by C.D. Godsil

• Book ID: 104156335
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 524 KB
• Volume: 255
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/s0024-3795(97)83595-1

✦ Synopsis

Let G be a graph with adjacency matrix A, and let I-be the set of all permutation matrices which commute with A. We call G compact if every doubly stochastic matrix which commutes with A is a convex combination of matrices from I'. We characterize the graphs for which S( A) = {I} and show that the automorphism group of a compact regular graph is generously transitive, i.e., given any two vertices, there is an automorphism which interchanges them. We also describe a polynomial time algorithm for determining whether a regular graph on a prime number of vertices is compact.