Cayley graphs of order \(kp\) are Hamiltonian for \(k < 48\). (English) Zbl 1441.05106

Summary: We provide a computer-assisted proof that if \(G\) is any finite group of order kp, where \(1 \leq k < 48\) and \(p\) is prime, then every connected Cayley graph on \(G\) is hamiltonian (unless \(kp = 2\)). As part of the proof, it is verified that every connected Cayley graph of order less than 48 is either hamiltonian connected or hamiltonian laceable (or has valence \(\leq 2)\).


05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C45 Eulerian and Hamiltonian graphs


GAP; SmallGrp
Full Text: DOI arXiv


[1] B. Alspach, Hamilton paths in Cayley graphs on Coxeter groups: I,Ars Math. Contemp.8 (2015), 35-53, doi:10.26493/1855-3974.509.d9d. · Zbl 1317.05083
[2] B. Alspach, C. C. Chen and K. McAvaney, On a class of Hamiltonian laceable3-regular graphs, Discrete Math.151(1996), 19-38, doi:10.1016/0012-365x(94)00077-v. · Zbl 0855.05078
[3] B. Alspach and Y. Qin, Hamilton-connected Cayley graphs on Hamiltonian groups,European J. Combin.22(2001), 777-787, doi:10.1006/eujc.2001.0456. · Zbl 0983.05050
[4] T. Araki, Hyper Hamiltonian laceability of Cayley graphs generated by transpositions,Networks48(2006), 121-124, doi:10.1002/net.20126. · Zbl 1117.05068
[5] H. U. Besche, B. Eick and E. O’Brien, SmallGrp – a GAP package, Version 1.3, 9 April 2018, https://gap-packages.github.io/smallgrp/.
[6] C. C. Chen and N. F. Quimpo, On strongly Hamiltonian abelian group graphs, in: K. L. McAvaney (ed.),Combinatorial Mathematics VIII, Springer, New York, volume 884 ofLecture Notes in Mathematics, pp. 23-34, 1981, proceedings of the Eighth Australian Conference held at Deakin University, Geelong, August 25 - 29, 1980. · Zbl 0468.05055
[7] S. J. Curran, D. Witte Morris and J. Morris, Cayley graphs of order16pare hamiltonian,Ars Math. Contemp.5(2012), 185-211, doi:10.26493/1855-3974.207.8e0.
[8] M. Dupuis and S. Wagon, Laceable knights,Ars Math. Contemp.9(2015), 115-124, doi: 10.26493/1855-3974.420.3c5. · Zbl 1329.05177
[9] B. Fuller,Finding CCA groups and graphs algorithmically, Master’s thesis, University of Lethbridge, 2017,http://hdl.handle.net/10133/4996.
[10] The GAP Group,GAP - Groups, Algorithms, and Programming, Version 4.8.7 (2017) and 4.8.10 (2018),http://www.gap-system.org.
[11] E. Ghaderpour and D. Witte Morris, Cayley graphs of order27pare hamiltonian,Int. J. Comb. 2011(2011), Article ID 206930, doi:10.1155/2011/206930. · Zbl 1236.05102
[12] E. Ghaderpour and D. Witte Morris, Cayley graphs of order30pare Hamiltonian,Discrete Math.312(2012), 3614-3625, doi:10.1016/j.disc.2012.08.017. · Zbl 1273.05098
[13] J. L. Gross and T. W. Tucker,Topological Graph Theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1987. · Zbl 0621.05013
[14] K. Helsgaun, LKH - an effective implementation of the Lin-Kernighan heuristic, Version 2.0.7, 2012,http://www.akira.ruc.dk/˜keld/research/LKH/. · Zbl 0969.90073
[15] K. Keating and D. Witte, On Hamilton cycles in Cayley graphs in groups with cyclic commutator subgroup, in: B. R. Alspach and C. D. Godsil (eds.),Cycles in Graphs, NorthHolland, Amsterdam, volume 115 ofNorth-Holland Mathematics Studies, pp. 89-102, 1985, doi:10.1016/s0304-0208(08)72999-2, papers from the workshop held at Simon Fraser University, Burnaby, B.C., July 5 - August 20, 1982. · Zbl 0573.05029
[16] K. Kutnar, D. Maruˇsiˇc, D. Witte Morris, J. Morris and P. ˇSparl, Hamiltonian cycles in Cayley graphs whose order has few prime factors,Ars Math. Contemp.5(2012), 27-71, doi:10.26493/ 1855-3974.177.341. · Zbl 1247.05103
[17] P. E. Schupp, On the structure of Hamiltonian cycles in Cayley graphs of finite quotients of the modular group,Theoret. Comput. Sci.204(1998), 233-248, doi:10.1016/s0304-3975(98) 00041-3. · Zbl 0913.68149
[18] Wikipedia contributors, Field norm — Wikipedia, The Free Encyclopedia, 2018,https: //en.wikipedia.org/wiki/Field_norm.
[19] Wikipedia contributors, Schur-Zassenhaus theorem — Wikipedia, The Free Encyclopedia, 2018,https://en.wikipedia.org/wiki/Schur-Zassenhaus_theorem.
[20] D. Witte, Cayley digraphs of prime-power order are hamiltonian,J. Comb. Theory Ser. B40 (1986), 107-112, doi:10.1016/0095-8956(86)90068-7. · Zbl 0558.05024
[21] D. Witte and J. A. Gallian, A survey: hamiltonian cycles in Cayley graphs,Discrete Math.51 (1984), 293-304, doi:10.1016/0012-365x(84)90010-4. · Zbl 0718.05038
[22] D. Witte Morris, Odd-order Cayley graphs with commutator subgroup of orderpqare hamiltonian,Ars Math. Contemp.8(2015), 1-28, doi:10.26493/1855-3974.330.0e6. · Zbl 1317.05088
[23] D. Witte Morris, Infinitely many nonsolvable groups whose Cayley graphs are hamiltonian,J. Algebra Comb. Discrete Struct. Appl.3(2016), 13-30, doi:10.13069/jacodesmath.66457. · Zbl 1425.05075
[24] D.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.