Authors: W.-H Lu, H. Ren , C. Yang Title: Lower bound on the number of Hamiltonian cycles of generalized Petersen graphs Source: Discussiones Mathematicae Graph Theory Received 11.04.2017, Revised 17.03.2018, Accepted 19.03.2018, doi: 10.7151/dmgt.2141 | |
Abstract: In this paper, we investigate the number of Hamiltonian cycles of a generalized Petersen graph P(N,k) and prove that [Ψ(P(N,3))≥slant N?α_{N},] where Ψ(P(N,3)) is the number of Hamiltonian cycles of P(N,3) and α_{N} satisfies that for any ϵ>0, there exists a positive integer M such that when N>M, [((1-ϵ)\frac{(1-r^{3})}{6r^{3}+5r^{2}+3})(\frac{1}{r})^{N+2}<α_{N}<((1+ϵ) \frac{(1-r^{3})}{6r^{3}+5r^{2}+3})(\frac{1}{r})^{N+2},] where \frac{1}{r}=\max{\left|\frac{1}{r_{j}}\right| : j=1,2,...,6} and each r_{j} is a root of equation x^{6}+x^{5}+x^{3}-1=0, r≈ 0.782. This shows that Ψ(P(N,3) is exponential in N and also deduces that the number of 1-factors of P(N,3) is exponential in N. | |
Keywords: generalized Petersen graph, Hamiltonian cycle, partition number, 1-factor | |
Links: |