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

Thumbnail Image
Date
2017
Authors
Dobson, Ted
Hujdurovic, Ademir
Kutnar, Klavdija
Morris, Joy
Journal Title
Journal ISSN
Volume Title
Publisher
The University of Queensland, Centre for Discrete Mathematics and Computing
Abstract
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.
Description
Diamond open access
Keywords
Vertex-transitive graphs , Digraphs , Automorphism , Colour preserving , Arc-orbit , Caley
Citation
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
Collections