Trivalent orbit polynomial graphs (Q1110532)

Let \(\Gamma\) be a graph and A(\(\Gamma)\) be the adjacency matrix of \(\Gamma\). Let \(\Omega\) (\(\Gamma)\) be the matrix algebra consisting of all polynomials in A(\(\Gamma)\). Let Aut \(\Gamma\) be the automorphism group of \(\Gamma\) and \(C_ 0,C_ 1,...,C_ m\) be the orbits of Aut \(\Gamma\) on \(V\Gamma\) \(\times V\Gamma\), where \(V\Gamma\) is the vertex-set of \(\Gamma\). Let \(B_ i\) be the matrix of \(C_ i\), i.e. \((B_ i)_{uv}=1\) if \((u,v)\in C_ i\) and \((B_ i)uv=0\) otherwise, \(0\leq i\leq m.\) A graph \(\Gamma\) is orbit polynomial if for every i, \(0\leq i\leq m\), \(B_ i\) is contained in \(\Omega\) (\(\Gamma)\). In particular each distance-transitive graph is orbit polynomial. Theorem. The nonsymmetric trivalent orbit polynomial graphs are: (a) \(C_ m\times K_ 2\), \(m\geq 3\), \(m=1,2,3,5,7,9,10\) or 11 (mod 12), (b) \(W_{2m}\), \(m\geq 2\), \(m=0,1,4,5,7,8\) or 11 (mod 12). Here \(W_{2m}\) is the Cayley graph of the cyclic group of order 2m with the generator \(\sigma\) with respect to the set \(\{\sigma,\sigma^{-1},\sigma^ m\}\).