Vertex-transitive graphs and their arc-types

Abstract

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 A_v 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 n₁ + n₂ + … + n_t + (m₁ + m₁) + (m₂ + m₂) + … + (m_s + m_s), where n₁, n₂, …, n_t are the sizes of the self-paired orbits, and m₁, m₁, m₂, m₂, …, m_s, m_s 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.