A note on compact graphs (Q1174181)

Let \(G\) be an undirected simple graph with adjacency matrix \(A\). By \(S(A)\) we denote the set of all doubly stochastic matrices which commute with \(A\). We say \(G\) is compact if the extreme points of \(S(A)\) are all integral. It is not hard to see that the integral extreme points of \(S(A)\) are precisely the permutation matrices which commute with \(A\). Note also that \(S(A)\) is closed under matrix multiplication. Compact graphs form a fairly restricted class, for example, any compact regular graph must be vertex-transitive. The main result of this paper is a simple polynomial time algorithm for deciding whether a graph \(H\) is isomorphic to a given compact graph \(G\). The bad news is that the problem of recognising whether a graph is compact is not even known to be in NP.