Almost all Cayley Graphs Are Hamiltonian
Acta Mathematica Sinica, English Series
Acta Mathematica Sinica,
Chinese Series
Adv Search »  
Acta Mathematica Sinica, English Series  1996, Vol. 12 Issue (2): 151-155    DOI: 10.1007/BF02108156
articles Current Issue | Next Issue | Archive | Adv Search  |   
Almost all Cayley Graphs Are Hamiltonian
Meng Jixiang, Huang Qiongxiang
Department of Mathematics and Institute of Mathematics and Phisics, Xinjiang University, 830046, Urumqi, China
 Download: PDF (108 KB)   HTML (0 KB)   Export: BibTeX | EndNote (RIS)      Supporting Info
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.
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
Articles by authors
Meng Jixiang
Huang Qiongxiang
Key wordsCayley graph   Hamiltonian   Random     
Received: 1994-03-07;
Fund: Supported by the National Natural Science Foundation of China, Xinjiang Educational Committee and Xinjiang University
Cite this article:   
Meng Jixiang,Huang Qiongxiang. Almost all Cayley Graphs Are Hamiltonian[J]. Acta Mathematica Sinica, English Series, 1996, 12(2): 151-155.
URL:      or
[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.
No Similar of article
  Copyright 2012 © Editorial Office of Acta Mathematica Sinica