Almost all Cayley Graphs Are Hamiltonian

Meng Jixiang, Huang Qiongxiang

Acta Mathematica Sinica ›› 1996, Vol. 12 ›› Issue (2) : 151-155.

PDF(108 KB)
PDF(108 KB)
Acta Mathematica Sinica ›› 1996, Vol. 12 ›› Issue (2) : 151-155. DOI: 10.1007/BF02108156
Articles

Almost all Cayley Graphs Are Hamiltonian

  • Meng Jixiang, Huang Qiongxiang
Author information +
History +

Abstract

It has been conjectured that there is a hamiltonian cycle in every finite connected Cayley graph. In spite of the difficulty in proving this conjecture, we show that almost all Cayley graphs are hamiltonian. That is, as the order n of a group G approaches infinity, the ratio of the number of hamiltonian Cayley graphs of G to the total number of Cayley graphs of G approaches1.

Key words

Cayley graph / Hamiltonian / Random

Cite this article

Download Citations
Meng Jixiang, Huang Qiongxiang. Almost all Cayley Graphs Are Hamiltonian. Acta Mathematica Sinica, 1996, 12(2): 151-155 https://doi.org/10.1007/BF02108156

References

[1] Guy, R., Hanani, H., Saver, I. V. and Schonheim, J. eds., Combinatorial Structures and Their Applications, Gordon and Breach, New York, 1970.
[2] Bondy, J. A., Hamiltonian cycles in graphs and digraphs, Proc. 9th S. E. Conf. Comb., Graph Theory and Computing, 1978, 3-28.
[3] Witte, D. and Gallian, J. A., A survey:Hamiltonian cycles in Cayley graphs,Discrete Math., 1984,51:293-304.
[4] Powers, D. L., Exceptional trivalent Cayley graphs for dihedral groups,J. Graph Theory, 1982,6:43-55.
[5] Wang Min and Fang Xin-gui, A discriminate condition of H-cycle on dihederal groups,J. Sys. Sci. and Math. Scis., 1992,12:169-173.
[6] Bondy, J. A. and Murty, U. S. R.,Graph Theory with Applications, New York, North Holland, 1979.
[7] Hall, M.,The Theory of Groups, New York:Macmillan, 1959.
[8] Bollobas, B.,Random Graphs, New York:Academic Press, 1985.
[9] Billingsley, P.,Probability and Measure, New York:John. Wiley and Sons, 1979.
[10] Babai, L. and Godsil, C. D., On the automorphism groups of almost all Cayley graphs,Europ. J. Combinatorics, 1982,3:9-15.
[11] Jackson, B., Hamiltonian cycles in regular 2-connected graphs,J. Combin. Theory, Ser. B 1980,29:27-46.
[12] Holsztynski, W. and Strube, R. F. E., Paths and circuits in finite groups,Discrete Math., 1978,22:263-272.
[13] Witte, D., Cayley diagrams of prime-power order are hamiltonian,J. Combin. Theory, 1986,408:107-112.
[14] Laffey, T. T., The number of solution ofxp =1 in a finite group,Math. Proc. Combridge Philos. Soc., 1976,80:229-231.
[15] Robbins, H., A remark on stirling's formula,Amer. Math. Monthly, 1955,62:26-29.
[16] Watkins, M. E., Connectivity of transitive graphs,J. Combin. Theory, 1970,8:23-29.

Funding

Supported by the National Natural Science Foundation of China, Xinjiang Educational Committee and Xinjiang University
PDF(108 KB)

302

Accesses

0

Citation

Detail

Sections
Recommended

/