Vertex-transitive digraphs with extra automorphisms that preserve the natural arc-colouring

Thumbnail Image
Dobson, Ted
Hujdurovic, Ademir
Kutnar, Klavdija
Morris, Joy
Journal Title
Journal ISSN
Volume Title
The University of Queensland, Centre for Discrete Mathematics and Computing
In a Cayley digraph on a group G, if a distinct colour is assigned to each arc-orbit under the left-regular action of G, it is not hard to show that the elements of the left-regular action of G are the only digraph automorphisms that preserve this colouring. In this paper, we show that the equivalent statement is not true in the most straightforward generalisation to G-vertex-transitive digraphs, even if we restrict the situation to avoid some obvious potential problems. Specifically, we display an infinite family of 2-closed groups G, and a G-arc-transitive digraph on each (without any digons) for which there exists an automorphism of the digraph that is not an element of G (it is an automorphism of G). Since the digraph is G-arc-transitive, the arcs would all be assigned the same colour under the colouring by arc-orbits, so this digraph automorphism is colour-preserving.
Diamond open access
Vertex-transitive graphs , Digraphs , Automorphism , Colour preserving , Arc-orbit , Caley
Dobson, T., Hujdurovic, A., Kutnar, K., & Morris, J. (2017). Vertex-transitive digraphs with extra automorphisms that perserve the natural arc-colouring. Australasian Journal of Combinatorics, 67(2), 88-100