The arc-types of Cayley graphs

Marston D. E. Conder ; Nemanja Poznanović

Ars Mathematica Contemporanea, Tome 15 (2018) no. 1, pp. 97-112.

Résumé

Let X be a finite vertex-transitive graph of valency d, and let A be the full automorphism group of X. Then the arc-type of X is defined in terms of the sizes of the orbits of the action of the stabiliser Av of a given vertex v on the set of arcs incident with v. Specifically, the arc-type is the partition of d as the sum n1 + n2 + … + nt + (m1 + m1) + (m2 + m2) + … + (ms + ms), where n1, n2, …, nt are the sizes of the self-paired orbits, and m1, m1, m2, m2, …, ms, ms are the sizes of the non-self-paired orbits, in descending order.In a recent paper, it was shown by Conder, Pisanski and Žitnik that with the exception of the partitions 1 + 1 and (1 + 1) for valency 2, every such partition occurs as the arc-type of some vertex-transitive graph. In this paper, we extend this to show that in fact every partition other than 1, 1 + 1 and (1 + 1) occurs as the arc-type of infinitely many connected finite Cayley graphs with the given valency d. As a consequence, this also shows that for every d > 2, there are infinitely many finite zero-symmetric graphs (or GRRs) of valency d.

Détail

DOI : 10.26493/1855-3974.1327.6ee

Keywords: Symmetry type, vertex-transitive graph, arc-transitive graph, Cayley graph, zero-symmetric graph, Cartesian product, covering graph