Lower Bound on the Number of Hamiltonian Cycles of Generalized Petersen Graphs

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))⩾N⋅αN,\Psi ( {P ( {N,3} )} ) \ge N \cdot {\alpha _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−ɛ)(1−r3)6r3+5r2+3)(1r)N+2<αN<((1+ɛ)(1−r3)6r3+5r2+3)(1r)N+2,\left( { ( {1 - \epsilon } ){{ ( {1 - {r^3}} )} \over {6{r^3} + 5{r^2} + 3}}} \right){ \left( {{1 \over r}} \right)^{N + 2}} < {\alpha _N} < \left( { ( {1 + \epsilon } ){{ ( {1 - {r^3}} )} \over {6{r^3} + 5{r^2} + 3}}} \right){ \left( {{1 \over r}} \right)^{N + 2}}, where 1r=max{|1rj|:j=1,2,…,6}{1 \over r} = \max \left\{ {\left| {{1 \over {{r_j}}}} \right|:j = 1,2, \ldots ,6} \right\} 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
• 05c30
• 05c45
• 05c70