Geodesic
Lower Bound on the Number of Hamiltonian Cycles of Generalized Petersen Graphs
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 297-305

Voir la notice de l'article provenant de la source Library of Science

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, where Ψ (P(N, 3)) is the number of Hamiltonian cycles of P(N, 3) and α_N satisfies that for any ϵ gt; 0, there exists a positive integer M such that when N gt; M, ((1− ϵ ) (1−r^3) /6r^3+5r^2+3) ( 1/r )^N+2 lt; α_N lt; ( (1+ɛ) (1−r^3) /6r^3+5r^2+3) ( 1/r )^N+2, where 1/r = max{ | 1/r_j | : 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 
@article{DMGT_2020_40_1_a19,
     author = {Lu, Weihua and Yang, Chao and Ren, Han},
     title = {Lower {Bound} on the {Number} of {Hamiltonian} {Cycles} of {Generalized} {Petersen} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {297--305},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a19/}
}
TY  - JOUR
AU  - Lu, Weihua
AU  - Yang, Chao
AU  - Ren, Han
TI  - Lower Bound on the Number of Hamiltonian Cycles of Generalized Petersen Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 297
EP  - 305
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a19/
LA  - en
ID  - DMGT_2020_40_1_a19
ER  - 
%0 Journal Article
%A Lu, Weihua
%A Yang, Chao
%A Ren, Han
%T Lower Bound on the Number of Hamiltonian Cycles of Generalized Petersen Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 297-305
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a19/
%G en
%F DMGT_2020_40_1_a19
Lu, Weihua; Yang, Chao; Ren, Han. Lower Bound on the Number of Hamiltonian Cycles of Generalized Petersen Graphs. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 297-305. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a19/