Hamiltonian Normal Cayley Graphs

Montellano-Ballesteros, Juan José ; Arguello, Anahy Santiago

Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 731-740.

Résumé

A variant of the Lovász Conjecture on hamiltonian paths states that every finite connected Cayley graph contains a hamiltonian cycle. Given a finite group G and a connection set S, the Cayley graph Cay(G, S) will be called normal if for every g ∈ G we have that g₋₁Sg = S. In this paper we present some conditions on the connection set of a normal Cayley graph which imply the existence of a hamiltonian cycle in the graph.

Détail

Keywords: Cayley graph, hamiltonian cycle, normal connection set

Bibliographie

[1] N. Alon and Y. Roichman, Random Cayley graphs and expanders, Random Structures Algorithms 5 (1994) 271–284. doi:10.1002/rsa.3240050203

[2] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, New York, 2008).

[3] J. Bourgain and A. Gamburd, Uniform expansion bounds for Cayley graphs of SL 2 (ℱ p ), Ann. of Math. 167 (2008) 625–642. doi:10.4007/annals.2008.167.625

[4] C.C. Chen and N. Quimpo, On strongly hamiltonian abelian group graphs, Combin. Math. VIII (Geelong, 1980) Lecture Notes in Math. 884 (Springer, Berlin-New York, 1981) 23–34.

[5] E. Durnberger, Connected Cayley graphs of semi-direct products of cyclic groups of prime order by abelian groups are hamiltonian, Discrete Math. 46 (1983) 55–68. doi:10.1016/0012-365X(83)90270-4

[6] E. Ghaderpour and D. Witte Morris, Cayley graphs on nilpotent groups with cyclic commutator subgroup are hamiltonian, Ars Math. Contemp. 7 (2014) 55–72. doi:10.26493/1855-3974.280.8d3

[7] H.H. Glover, K. Kutnar, A. Malnič and D. Marušič, Hamilton cycles in (2, odd, 3) - Cayley graphs, Proc. Lond. Math. Soc. 104 (2012) 1171–1197. doi:10.1112/plms/pdr042

[8] H.H. Glover, K. Kutnar and D. Marušič, Hamiltonian cycles in cubic Cayley graphs: the < 2, 4 k, 3 > case, J. Algebraic Combin. 30 (2009) 447–475. doi:10.1007/s10801-009-0172-5

[9] H.H. Glover and D. Marušič, Hamiltonicity of cubic Cayley graph, J. Eur. Math. Soc. 9 (2007) 775–787.

[10] H.H. Glover and T.Y. Yang, A Hamilton cycle in the Cayley graph of the (2, p, 3) - presentation of PSL 2( p ), Discrete Math. 160 (1996) 149–163. doi:10.1016/0012-365X(95)00155-P

[11] K. Keating and D. Witte, On Hamilton cycles in Cayley graphs in groups with cyclic commutator subgroup, Annals of Discrete Math. 27 (1985) 89–102.

[12] K. Kutnar, D. Marušič, D. Morris, J. Morris and P. Šparl, Hamiltonian cycles in Cayley graphs of small order, Ars Math. Contemp. 5 (2012) 27–71. doi:10.26493/1855-3974.177.341

[13] D. Marušič, Hamilonian circuits in Cayley graphs, Discrete Math. 46 (1983) 49–54. doi:10.1016/0012-365X(83)90269-8

[14] I. Pak and R. Radoičić, Hamiltonian paths in Cayley graphs, Discrete Math. 309 (2009) 5501–5508. doi:0.1016/j.disc.2009.02.018

[15] C. Praeger, Finite normal edge-transitive Cayley graphs, Bull. Aust. Math. Soc. 60 (1999) 207–220. doi:10.1017/S0004972700036340

[16] J.J. Rotman, An Introduction to the Theory of Groups, Fourth Edition (Springer-Verlag, New York, 1995).

[17] F. Menegazzo, The number of generator of a finite group, Irish Math. Soc. Bull. 50 (2003) 117–128.

[18] 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

[19] C. Wang, D. Wang and M. Xu, Normal Cayley graphs of finite groups, Sci. China Ser. A 41 (1998) 242–251. doi:10.1007/BF02879042

[20] D. Witte Morris, Odd-order Cayley graphs with commutator subgroup of order pq are hamiltonian, Ars Math. Contemp. 8 (2015) 1–28. doi:10.26493/1855-3974.330.0e6