Almost all Cayley graphs are hamiltonian |
| |
Authors: | Meng Jixiang Huang Qiongxiang |
| |
Affiliation: | (1) 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 groupG approaches infinity, the ratio of the number of hamiltonian Cayley graphs ofG to the total number of Cayley graphs ofG approaches 1.Supported by the National Natural Science Foundation of China, Xinjiang Educational Committee and Xinjiang University. |
| |
Keywords: | Cayley graph Hamiltonian Random |
本文献已被 SpringerLink 等数据库收录! |