Back to Search Start Over

Infinite Families of Vertex-Transitive Graphs with Prescribed Hamilton Compression.

Infinite Families of Vertex-Transitive Graphs with Prescribed Hamilton Compression.

Authors :
Kutnar, Klavdija
Marušič, Dragan
Razafimahatratra, Andriaherimanana Sarobidy
Source :
Annals of Combinatorics. Dec2024, Vol. 28 Issue 4, p1243-1255. 13p.
Publication Year :
2024

Abstract

Given a graph X with a Hamilton cycle C, the compression factor κ (X , C) of C is the order of the largest cyclic subgroup of Aut (C) ∩ Aut (X) , and the Hamilton compression κ (X) of X is the maximum of κ (X , C) where C runs over all Hamilton cycles in X. Generalizing the well-known open problem regarding the existence of vertex-transitive graphs without Hamilton paths/cycles, it was asked by Gregor et al. (Ann Comb, arXiv:2205.08126v1, https://doi.org/10.1007/s00026-023-00674-y, 2023) whether for every positive integer k, there exists infinitely many vertex-transitive graphs (Cayley graphs) with Hamilton compression equal to k. Since an infinite family of Cayley graphs with Hamilton compression equal to 1 was given there, the question is completely resolved in this paper in the case of Cayley graphs with a construction of Cayley graphs of semidirect products Z p ⋊ Z k where p is a prime and k ≥ 2 a divisor of p - 1 . Further, infinite families of non-Cayley vertex-transitive graphs with Hamilton compression equal to 1 are given. All of these graphs being metacirculants, some additional results on Hamilton compression of metacirculants of specific orders are also given. [ABSTRACT FROM AUTHOR]

Subjects

Subjects :
*CAYLEY graphs
*INTEGERS

Details

Language :
English
ISSN :
02180006
Volume :
28
Issue :
4
Database :
Academic Search Index
Journal :
Annals of Combinatorics
Publication Type :
Academic Journal
Accession number :
180971889
Full Text :
https://doi.org/10.1007/s00026-024-00703-4