Compact graphs and equitable partitions Original Research Article

Let G be a graph with adjacency matrix A, and let Γ 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 Γ. 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.