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/

[1] B. Alspach, The classification of Hamiltonian generalized Petersen graphs, J. Combin. Theory Ser. B 34 (1983) 293–312. doi:10.1016/0095-8956(83)90042-4

[2] K. Bannai, Hamiltonian cycles in generalized Petersen graphs, J. Combin. Theory Ser. B 24 (1978) 181–188. doi:10.1016/0095-8956(78)90019-9

[3] J.A. Bondy, Variations on the Hamiltonian theme, Canad. Math. Bull. 15 (1972) 57–62. doi:10.4153/CMB-1972-012-3

[4] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

[5] F. Castagna and G. Prins, Every generalized Petersen graph has a Tait coloring, Pacific J. Math. 40 (1972) 53–58. doi:10.2140/pjm.1972.40.53

[6] C. Cooper and A.M. Frieze, On the number of Hamiltonian cycles in a random graph, J. Graph Theory 13 (1989) 719–735. doi:10.1002/jgt.3190130608

[7] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).

[8] C.H. Papadimitriou, Computational Complexity (Addison-Wesley, Reading, MA, 1994).

[9] G.N. Robertson, Graphs under Girth, Valency, and Connectivity Constraints, PhD. Thesis (University of Waterloo, Ontario, Canada, 1968).

[10] A. Schwenk, Enumeration of Hamiltonian cycles in certain generalized Petersen graphs, J. Combin. Theory Ser. B 47 (1989) 53–59. doi:10.1016/0095-8956(89)90064-6

[11] A. Thomason, Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable, J. Graph Theory 6 (1982) 219–221. doi:10.1002/jgt.3190060218

[12] A.G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs, Ann. Discrete Math. 3 (1978) 259–268. doi:10.1016/S0167-5060(08)70511-9

[13] W.T. Tutte, On Hamiltonian circuits, J. Lond. Math. Soc. (2) 21 (1946) 98–101. doi:10.1112/jlms/s1-21.2.98

[14] M.E. Watkins, A theorem on tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory 6 (1969) 152–164. doi:10.1016/S0021-9800(69)80116-X