Orbit polynomial graphs of prime order (Q1101127)

Let \({\mathcal A}(\Gamma)\) denote the algebra of polynomials of the adjacency matrix A of a finite simple graph \(\Gamma\). Then dim \({\mathcal A}(\Gamma)=e(\Gamma)\), the number of distinct eigenvalues of A. Let \(C_ 0,C_ 1,...,C_ m\) be the orbits of the action of Aut(\(\Gamma)\) on the set \(V(\Gamma) \times V(\Gamma)\). For \(k=0,1,...,m\), let \(B_ k\) be the matrix whose (x,y)-entry is 1 if \((x,y)\in C_ k\) and is 0 otherwise. Theorem 2.1: for all \(\Gamma\), \({\mathcal A}(\Gamma)\leq <\{B_ 0,B_ 1,...,B_ m\}>.\) We call \(\Gamma\) orbit polynomial if \(B_ k\in {\mathcal A}(\Gamma)\) for all k. All distance-transitive graphs are orbit polynomial. Among others, the following further results are obtained: All orbit polynomial graphs are connected and vertex transitive; the converse holds for graphs of prime order. The following are equivalent for all \(\Gamma\): (a) \(\Gamma\) is orbit polynomial; (b) \(e(\Gamma)=m+1\); (c) \(\{B_ 0,B_ 1,...,B_ m\}\) is a basis for \({\mathcal A}(\Gamma)\). Finally, the distance-transitive graphs of prime order are completely described.