Hamiltonian decomposition of Cayley graphs of ordersp 2 andpq
Tóm tắt
In this paper, it is proved that any connected Cayley graph on an abelian group of order pq orp
2 has a hamiltonian decomposition, wherep andq are odd primes. This result answers partially a conjecture of Alspach concerning hamiltonian decomposition of 2k-regular connected Cayley graphs on abelian groups.
Tài liệu tham khảo
H.P. Yap. Some Topics in Graph Theory. Cambridge University Press, London, 1986
D. Marusic. Hamiltonian Circuit in Cayley Graphs.Discrete Mathematics, 1984, 51: 293–304
B. Alspach. Research Problem 59.Discrete Mathematics, 1984, 50: 115
J.C. Bermond, O. Favaron, M. Maheo. Hamiltonian Decomposition of Cayley Graphs of Degree 4.Journal of Combinatorial Theory (Series B), 1989, 46: 142–153
Liu Jiping. The Hamiltonian Decomposition of Certain Circulant Graphs.Ann. Discrete Mathematics, 1993, 55: 367–373.
Liu Jiuqiang. Hamiltonian Decomposition of Cayley Graphs on Abelian Group of Odd Order.Journal of Combinatorial Theory (Series B), 1996, 66: 75–86.