Vertex-transitive graphs and their arc-types

Marston D. E. Conder ; Tomaž Pisanski ; Arjana Žitnik

Ars Mathematica Contemporanea, Tome 12 (2017) no. 2, pp. 383-413.

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 stabiliser Av of a given vertex v on the set of arcs incident with v. Such an orbit is said to be self-paired if it is contained in an orbit Δ  of A on the set of all arcs of X such that Δ  is closed under arc-reversal. The arc-type of X is then 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 this paper, we find the arc-types of several families of graphs. Also we show that the arc-type of a Cartesian product of two ‘relatively prime’ graphs is the natural sum of their arc-types. Then using these observations, we show that with the exception of 1 + 1 and (1 + 1), every partition as defined above is realisable, in the sense that there exists at least one vertex-transitive graph with the given partition as its arc-type.

Détail

DOI : 10.26493/1855-3974.1146.f96

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