On orders of automorphisms of vertex-transitive graphs

In this paper we investigate orders, longest cycles and the number of cycles of automorphisms of finite vertex-transitive graphs. In particular, we show that the order of every automorphism of a connected vertex-transitive graph with n vertices and of valence d, d <= 4, is at most c(d)n where c(3) = 1 and c(4) = 9. Whether such a constant c(d) exists for valencies larger than 4 remains an unanswered question. Further, we prove that every automorphism g of a finite connected 3-valent vertex-transitive graph Gamma, Gamma not congruent to K-3,K-3, has a regular orbit, that is, an orbit of < g > of length equal to the order of g. Moreover, we prove that in this case either Gamma belongs to a well understood family of exceptional graphs or at least 5/12 of the vertices of Gamma belong to a regular orbit of g. Finally, we give an upper bound on the number of orbits of a cyclic group of automorphisms C of a connected 3-valent vertex-transitive graph Gamma in terms of the number of vertices of Gamma and the length of a longest orbit of C. (c) 2024 The Authors. Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).