Almost all Cayley Graphs Are Hamiltonian
Meng Jixiang, Huang Qiongxiang
Department of Mathematics and Institute of Mathematics and Phisics, Xinjiang University, 830046, Urumqi, China
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
Fund: Supported by the National Natural Science Foundation of China, Xinjiang Educational Committee and Xinjiang University
Guy, R., Hanani, H., Saver, I. V. and Schonheim, J. eds., Combinatorial Structures and Their Applications, Gordon and Breach, New York, 1970.
Bondy, J. A., Hamiltonian cycles in graphs and digraphs, Proc. 9th S. E. Conf. Comb., Graph Theory and Computing, 1978, 3-28.
Witte, D. and Gallian, J. A., A survey:Hamiltonian cycles in Cayley graphs,
Discrete Math., 1984, 51:293-304.
Powers, D. L., Exceptional trivalent Cayley graphs for dihedral groups,
J. Graph Theory, 1982, 6:43-55.
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.
Bondy, J. A. and Murty, U. S. R.,
Graph Theory with Applications, New York, North Holland, 1979.
The Theory of Groups, New York:Macmillan, 1959.
Random Graphs, New York:Academic Press, 1985.
Probability and Measure, New York:John. Wiley and Sons, 1979.
Babai, L. and Godsil, C. D., On the automorphism groups of almost all Cayley graphs,
Europ. J. Combinatorics, 1982, 3:9-15.
Jackson, B., Hamiltonian cycles in regular 2-connected graphs,
J. Combin. Theory, Ser. B 1980, 29:27-46.
Holsztynski, W. and Strube, R. F. E., Paths and circuits in finite groups,
Discrete Math., 1978, 22:263-272.
Witte, D., Cayley diagrams of prime-power order are hamiltonian,
J. Combin. Theory, 1986, 408:107-112.
Laffey, T. T., The number of solution of
x =1 in a finite group, p Math. Proc. Combridge Philos. Soc., 1976, 80:229-231.
Robbins, H., A remark on stirling's formula,
Amer. Math. Monthly, 1955, 62:26-29.
Watkins, M. E., Connectivity of transitive graphs,
J. Combin. Theory, 1970, 8:23-29.