Hamiltonian cycles in cubic Cayley graphs: the \langle 2,4 k,3\rangle case
Henry H. Glover
, Klavdija Kutnar
and Dragan Marušič
DOI: 10.1007/s10801-009-0172-5
Abstract
It was proved by Glover and Marušič (J. Eur. Math. Soc. 9:775-787, 2007), that cubic Cayley graphs arising from groups G=\langle a, x\mid a 2= x s =( ax) 3=1,\cdots \rangle having a (2, s,3)-presentation, that is, from groups generated by an involution a and an element x of order s such that their product ax has order 3, have a Hamiltonian cycle when | G| (and thus also s) is congruent to 2 modulo 4, and have a Hamiltonian path when | G| is congruent to 0 modulo 4.
In this article the existence of a Hamiltonian cycle is proved when apart from | G| also s is congruent to 0 modulo 4, thus leaving | G| congruent to 0 modulo 4 with s either odd or congruent to 2 modulo 4 as the only remaining cases to be dealt with in order to establish existence of Hamiltonian cycles for this particular class of cubic Cayley graphs.
Pages: 447–475
Keywords: keywords Hamiltonian cycle; Cayley graph; cubic arc-transitive graph; consistent cycle; cyclic edge connectivity
Full Text: PDF
References
1. Alspach, B.: Hamiltonian cycles in vertex-transitive graphs of order 2p. In: Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, FL, 1979). Congress. Numer., vol. XXIII-XX, pp. 131-139. Winnipeg, Manitoba (1979)
2. Alspach, B., Zhang, C.Q.: Hamilton cycles in cubic Cayley graphs on dihedral groups. Ars Comb. 28, 101-108 (1989)
3. Anderson, M.S., Richter, R.B.: Self-dual Cayley maps. Eur. J. Comb. 21, 419-430 (2000)
4. Biggs, N.: Aspects of symmetry in graphs. In: Algebraic methods in graph theory, vols. I, II, Szeged,
1978. Colloq. Math. Soc. János Bolyai, vol. 25, pp. 27-35. North-Holland, Amsterdam (1981)
5. Bouwer, I.Z. (ed.): The Foster Census. Winnipeg, Manitoba (1988)
6. Chen, Y.Q.: On Hamiltonicity of vertex-transitive graphs and digraphs of order p4. J. Comb. Theory Ser. B 72, 110-121 (1998)
7. Conder, M.D.E., Dobcsanyi, P.: Trivalent symmetric graphs on up to 768 vertices. J. Comb. Math. Comb. Comput. 40, 41-63 (2002)
8. Conder, M.D.E., Jajcay, R., Tucker, T.: Regular t -balanced Cayley maps. J. Comb. Theory, Ser. B 97, 453-473 (2007)
9. Conder, M.D.E., Nedela, R.: Symmetric cubic graphs of small girth. J. Comb. Theory, Ser. B 97, 757-768 (2007)
10. Conder, M.D.E., Nedela, R.: A more detailed classification of symmetric cubic graphs. Preprint
11. Conway, J.H.: Talk given at the Second British Combinatorial Conference at Royal Holloway College (1971)
12. Curran, S., Gallian, J.A.: Hamiltonian cycles and paths in Cayley graphs and digraphs-a survey. Discrete Math. 156, 1-18 (1996)
13. Durnberger, E.: Connected Cayley graphs of semidirect products of cyclic groups of prime order by Abelian groups are Hamiltonian. Discrete Math. 46, 55-68 (1983)
14. Dobson, E., Gavlas, H., Morris, J., Witte, D.: Automorphism groups with cyclic commutator subgroup and Hamilton cycles. Discrete Math. 189, 69-78 (1998)
15. Feng, Y.Q., Nedela, R.: Symmetric cubic graphs of girth at most
7. Acta Univ. M. Belii Math. 13, 33-55 (2006)
16. Frucht, R.: How to describe a graph. Ann. N.Y. Acad. Sci. 175, 159-167 (1970)
17. Frucht, R., Graver, J.E., Watkins, M.E.: The groups of the generalized Petersen graphs. Proc. Camb. Philos. Soc. 70, 211-218 (1971)
18. Glover, H.H., Maruši\check c, D.: Hamiltonicity of cubic Cayley graphs. J. Eur. Math. Soc. 9, 775-787 (2007)
19. Glover, H.H., Yang, T.Y.: A Hamilton cycle in the Cayley graph of the (2, p, 3)-presentation of P SL2(p). Discrete Math. 160, 149-163 (1996)
20. Horton, J.D., Bouwer, I.Z.: Symmetric Y -graphs and H -graphs. J. Comb. Theory, Ser. B 53, 114-129 (1991)
21. Jajcay, R.: Automorphism groups of Cayley maps. J. Comb. Theory, Ser. B 59, 297-310 (1993)
22. Jajcay, R., Širá\check n, J.: Skew-morphisms of regular Cayley maps. Discrete Math. 244, 167-179 (2002)
23. Jones, G.A., Surowski, D.B.: Regular cyclic coverings of the Platonic maps. Eur. J. Comb. 21, 333- 345 (2000)
24. Keating, K., Witte, D.: On Hamilton cycles in Cayley graphs in groups with cyclic commutator subgroup. In: Cycles in Graphs, Burnaby, B.C.,
1982. North-Holland Math. Stud., vol. 115, pp. 89-102. North-Holland, Amsterdam (1985)
25. Kutnar, K., Maruši\check c, D.: Hamiltonicity of vertex-transitive graphs of order 4p. Eur. J. Comb. 29, 423-438 (2008)
26. Kutnar, K., Maruši\check c, D.: A complete classification of cubic symmetric graphs of girth
6. J. Comb. Theory, Ser. B 99, 162-184 (2009)
27. Lovász, L.: Combinatorial structures and their applications. In: Proc. Calgary Int. Conf., Calgary, Alberta,
1969. Problem, vol. 11, pp. 243-246. Gordon and Breach, New York (1970)
28. Maruši\check c, D.: Hamilonian circuits in Cayley graphs. Discrete Math. 46, 49-54 (1983)
29. Maruši\check c, D.: Vertex transitive graphs and digraphs of order pk . In: Cycles in graphs, Burnaby, B.C.,
1982. Ann. Discrete Math., vol. 27, pp. 115-128. North-Holland, Amsterdam (1985)
30. Maruši\check c, D.: Hamiltonian cycles in vertex symmetric graphs of order 2p2. Discrete Math. 66, 169- 174 (1987)
31. Maruši\check c, D.: On vertex-transitive graphs of order qp. J. Comb. Math. Comb. Comput. 4, 97-114 (1988)
32. Maruši\check c, D., Parsons, T.D.: Hamiltonian paths in vertex-symmetric graphs of order 5p. Discrete Math. 42, 227-242 (1982)
33. Maruši\check c, D., Parsons, T.D.: Hamiltonian paths in vertex-symmetric graphs of order 4p. Discrete Math. 43, 91-96 (1983)
34. Miklavi\check c, Š., Poto\check cnik, P., Willson, S.: Consistent cycles in graphs and digraphs. Graphs Comb. 23, 205-216 (2007)
35. Nedela, R., Škoviera, M.: Atoms of cyclic connectivity in cubic graphs. Math. Slovaca 45, 481-499 (1995)
36. Payan, C., Sakarovitch, M.: Ensembles cycliquement stables et graphes cubiques. Cahiers Centre Études Rech. Opér. 17, 319-343 (1975)
37. Richter, R.B., Širá\check n, J., Jajcay, R., Tucker, T.W., Watkins, M.E.: Cayley maps. J. Comb. Theory, Ser.
2. Alspach, B., Zhang, C.Q.: Hamilton cycles in cubic Cayley graphs on dihedral groups. Ars Comb. 28, 101-108 (1989)
3. Anderson, M.S., Richter, R.B.: Self-dual Cayley maps. Eur. J. Comb. 21, 419-430 (2000)
4. Biggs, N.: Aspects of symmetry in graphs. In: Algebraic methods in graph theory, vols. I, II, Szeged,
1978. Colloq. Math. Soc. János Bolyai, vol. 25, pp. 27-35. North-Holland, Amsterdam (1981)
5. Bouwer, I.Z. (ed.): The Foster Census. Winnipeg, Manitoba (1988)
6. Chen, Y.Q.: On Hamiltonicity of vertex-transitive graphs and digraphs of order p4. J. Comb. Theory Ser. B 72, 110-121 (1998)
7. Conder, M.D.E., Dobcsanyi, P.: Trivalent symmetric graphs on up to 768 vertices. J. Comb. Math. Comb. Comput. 40, 41-63 (2002)
8. Conder, M.D.E., Jajcay, R., Tucker, T.: Regular t -balanced Cayley maps. J. Comb. Theory, Ser. B 97, 453-473 (2007)
9. Conder, M.D.E., Nedela, R.: Symmetric cubic graphs of small girth. J. Comb. Theory, Ser. B 97, 757-768 (2007)
10. Conder, M.D.E., Nedela, R.: A more detailed classification of symmetric cubic graphs. Preprint
11. Conway, J.H.: Talk given at the Second British Combinatorial Conference at Royal Holloway College (1971)
12. Curran, S., Gallian, J.A.: Hamiltonian cycles and paths in Cayley graphs and digraphs-a survey. Discrete Math. 156, 1-18 (1996)
13. Durnberger, E.: Connected Cayley graphs of semidirect products of cyclic groups of prime order by Abelian groups are Hamiltonian. Discrete Math. 46, 55-68 (1983)
14. Dobson, E., Gavlas, H., Morris, J., Witte, D.: Automorphism groups with cyclic commutator subgroup and Hamilton cycles. Discrete Math. 189, 69-78 (1998)
15. Feng, Y.Q., Nedela, R.: Symmetric cubic graphs of girth at most
7. Acta Univ. M. Belii Math. 13, 33-55 (2006)
16. Frucht, R.: How to describe a graph. Ann. N.Y. Acad. Sci. 175, 159-167 (1970)
17. Frucht, R., Graver, J.E., Watkins, M.E.: The groups of the generalized Petersen graphs. Proc. Camb. Philos. Soc. 70, 211-218 (1971)
18. Glover, H.H., Maruši\check c, D.: Hamiltonicity of cubic Cayley graphs. J. Eur. Math. Soc. 9, 775-787 (2007)
19. Glover, H.H., Yang, T.Y.: A Hamilton cycle in the Cayley graph of the (2, p, 3)-presentation of P SL2(p). Discrete Math. 160, 149-163 (1996)
20. Horton, J.D., Bouwer, I.Z.: Symmetric Y -graphs and H -graphs. J. Comb. Theory, Ser. B 53, 114-129 (1991)
21. Jajcay, R.: Automorphism groups of Cayley maps. J. Comb. Theory, Ser. B 59, 297-310 (1993)
22. Jajcay, R., Širá\check n, J.: Skew-morphisms of regular Cayley maps. Discrete Math. 244, 167-179 (2002)
23. Jones, G.A., Surowski, D.B.: Regular cyclic coverings of the Platonic maps. Eur. J. Comb. 21, 333- 345 (2000)
24. Keating, K., Witte, D.: On Hamilton cycles in Cayley graphs in groups with cyclic commutator subgroup. In: Cycles in Graphs, Burnaby, B.C.,
1982. North-Holland Math. Stud., vol. 115, pp. 89-102. North-Holland, Amsterdam (1985)
25. Kutnar, K., Maruši\check c, D.: Hamiltonicity of vertex-transitive graphs of order 4p. Eur. J. Comb. 29, 423-438 (2008)
26. Kutnar, K., Maruši\check c, D.: A complete classification of cubic symmetric graphs of girth
6. J. Comb. Theory, Ser. B 99, 162-184 (2009)
27. Lovász, L.: Combinatorial structures and their applications. In: Proc. Calgary Int. Conf., Calgary, Alberta,
1969. Problem, vol. 11, pp. 243-246. Gordon and Breach, New York (1970)
28. Maruši\check c, D.: Hamilonian circuits in Cayley graphs. Discrete Math. 46, 49-54 (1983)
29. Maruši\check c, D.: Vertex transitive graphs and digraphs of order pk . In: Cycles in graphs, Burnaby, B.C.,
1982. Ann. Discrete Math., vol. 27, pp. 115-128. North-Holland, Amsterdam (1985)
30. Maruši\check c, D.: Hamiltonian cycles in vertex symmetric graphs of order 2p2. Discrete Math. 66, 169- 174 (1987)
31. Maruši\check c, D.: On vertex-transitive graphs of order qp. J. Comb. Math. Comb. Comput. 4, 97-114 (1988)
32. Maruši\check c, D., Parsons, T.D.: Hamiltonian paths in vertex-symmetric graphs of order 5p. Discrete Math. 42, 227-242 (1982)
33. Maruši\check c, D., Parsons, T.D.: Hamiltonian paths in vertex-symmetric graphs of order 4p. Discrete Math. 43, 91-96 (1983)
34. Miklavi\check c, Š., Poto\check cnik, P., Willson, S.: Consistent cycles in graphs and digraphs. Graphs Comb. 23, 205-216 (2007)
35. Nedela, R., Škoviera, M.: Atoms of cyclic connectivity in cubic graphs. Math. Slovaca 45, 481-499 (1995)
36. Payan, C., Sakarovitch, M.: Ensembles cycliquement stables et graphes cubiques. Cahiers Centre Études Rech. Opér. 17, 319-343 (1975)
37. Richter, R.B., Širá\check n, J., Jajcay, R., Tucker, T.W., Watkins, M.E.: Cayley maps. J. Comb. Theory, Ser.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition