Vertex-transitive graphs and their arc-types

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


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.


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

Full Text:


ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications