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.
- 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 :
- *CAYLEY graphs
*INTEGERS
Subjects
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