### 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*_{1} + *n*_{2} + … + *n*_{t} + (*m*_{1} + *m*_{1}) + (*m*_{2} + *m*_{2}) + … + (*m*_{s} + *m*_{s}), where *n*_{1}, *n*_{2}, …, *n*_{t} are the sizes of the self-paired orbits, and *m*_{1}, *m*_{1}, *m*_{2}, *m*_{2}, …, *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.

#### Keywords

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