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-r3)}{6r3+5r2+3})(\frac{1}{r})N+2<αN<((1+ϵ) \frac{(1-r3)}{6r3+5r2+3})(\frac{1}{r})N+2,] where \frac{1}{r}=\max{\left|\frac{1}{rj}\right| : j=1,2,...,6} and each rj is a root of equation x6+x5+x3-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: PDF