Orbit polynomial graphs of prime order (Q1101127)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Orbit polynomial graphs of prime order |
scientific article |
Statements
Orbit polynomial graphs of prime order (English)
0 references
1987
0 references
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.
0 references
adjacency algebra
0 references
distance regular
0 references
distance-polynomial
0 references
distance- transitive graphs
0 references
orbit polynomial graphs
0 references
0 references