A survey on Hamiltonian Cycle in Cayley graphs

Document Type : Research Paper

Authors

Faculty of Mathematical and Computer Science, Kharazmi University, Tehran, Iran;

Abstract

It has been conjectured there is a Hamiltonian cycle in every Cayley graph. Interest in this and other closely related questions has grown in the past few years. There have been many papers on the topic, but it is still an open question whether every connected Cayley graph has a Hamiltonian cycle. In this paper, we survey the results, techniques, and open problems in the field.

Keywords

References

1. C. C. Chen, N. F. Quimpo, On some classes of Hamiltonian graphs, Southeast Asian Bull, Math, (1979). 
2. C. Godsil, G. Royle, Algebraic Graph Theory, Springer, New York, (2001).
3. J. L. Gross, T. W. Tucker, Topological Graph Theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley and Sons, New York, (1987).
4. K. Helsgaun, LKH–an effective implementation of the Lin-Kernighan heuristic (version 2.0.7), (2012).
5. I. M. Isaacs, Finite group theory, American Mathematical Soc, 10 (2008).
6. K. Kutnar, D. Marusic, D. W. Morris, J. Morris, P. Sparl, Hamiltonian cycles in Cayley graphs whose order has few prime factors, Ars Math. Contemp, 1009–5795 (2012).
7. D. W. Morris, Odd-order Cayley graphs with commutator subgroup of order pq are Hamiltonian, Ars Math. Contemp, 1205–0087 (2015).
8. D. W. Morris, Infinitely many nonsolvable groups whose Cayley graphs are Hamiltonian, J. Algebra Combin. Discrete Struct. Appl. 13–30 (2015).
9. C. Savage, A survey of combinatorial Gray codes, SIAM Rev, Contemp, 605-629 (1997).
10. D. Witte, J. A. Gallian, A survey: Hamiltonian cycles in Cayley graphs, Discrete Mathematics, 293–304 (1984).
11. B. Alspach, C . C. Chen, M. Dean, Hamilton paths in Cayley graphs on generalized dihedral groups, ARS Mathematica Contemporanea, 3(1), (2010). 
Analytical and Numerical Solutions for Nonlinear Equations
Volume 8, Issue 1
November 2023
Pages 97-103

Files

History

  • Receive Date: 05 October 2023
  • Revise Date: 07 April 2024
  • Accept Date: 08 April 2024

Share

How to cite

Statistics