# Vertex-transitive graphs and their arc-types

## DOI:

https://doi.org/10.26493/1855-3974.1146.f96## Keywords:

Symmetry type, vertex-transitive graph, arc-transitive graph, Cayley graph, Cartesian product, covering graph## 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.

## Downloads

## Published

## Issue

## Section

## License

Articles in this journal are published under Creative Commons Attribution 4.0 International License

https://creativecommons.org/licenses/by/4.0/