Trivalent orbit polynomial graphs
type: Item
instance of: scholarly article
title: Trivalent orbit polynomial graphs
zbMATH Open document ID: 0657.05036
DOI: 10.1016/0024-3795(86)90235-1
author: Robert A. Beezer
published in: Linear Algebra and its Applications
publication date: 1986-01-01T00:00:00Z
review text: 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\}\).
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 4073005
zbMATH Keywords: matrix algebra
zbMATH Keywords: distance-transitive graph
zbMATH Keywords: orbit polynomial graphs
zbMATH Keywords: Cayley graph
zbMATH Keywords: cyclic group
reviewed by: Aleksandr A. Ivanov
MaRDI profile type: Publication
full work available at URL: 0024-3795(86)90235-1
OpenAlex ID: W2003067798
cites work: Q4863413
cites work: On the polynomial of a path
cites work: Algebraic Graph Theory
cites work: The group and the minimal polynomial of a graph
cites work: Q5677530
cites work: Characterization of H(n,q) by the parameters
cites work: On finite linear groups
cites work: Q5572939
cites work: Some results on roots of unity, with an application to a diophantine problem
cites work: Graph multiplication
cites work: Q3037476
cites work: On distance-regularity in graphs
description: scientific article; zbMATH DE number 4073005