Department of Mathematics and Institute of Mathematics and Phisics, Xinjiang University, 830046, Urumqi, China
{{custom_zuoZheDiZhi}}
{{custom_authorNodes}}
{{custom_bio.content}}
{{custom_bio.content}}
{{custom_authorNodes}}
Collapse
History+
Received
Published
1994-03-07
1996-06-15
Issue Date
1996-06-15
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.
Meng Jixiang, Huang Qiongxiang.
Almost all Cayley Graphs Are Hamiltonian. Acta Mathematica Sinica, 1996, 12(2): 151-155 https://doi.org/10.1007/BF02108156
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
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.
{{custom_fnGroup.title_en}}
Footnotes
{{custom_fn.content}}
Funding
Supported by the National Natural Science Foundation of China, Xinjiang Educational Committee and Xinjiang University