Geodesic
Hamilton Cycles in Double Generalized Petersen Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 117-123

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

Coxeter referred to generalizing the Petersen graph. Zhou and Feng modified the graphs and introduced the double generalized Petersen graphs (DGPGs). Kutnar and Petecki proved that DGPGs are Hamiltonian in special cases and conjectured that all DGPGs are Hamiltonian. In this paper, we prove the conjecture by constructing Hamilton cycles in any given DGPG.
Keywords: double generalized Petersen graph, Hamilton cycle 
Sakamoto, Yutaro. Hamilton Cycles in Double Generalized Petersen Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 117-123. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a9/
@article{DMGT_2019_39_1_a9,
     author = {Sakamoto, Yutaro},
     title = {Hamilton {Cycles} in {Double} {Generalized} {Petersen} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {117--123},
     year = {2019},
     volume = {39},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a9/}
}
TY  - JOUR
AU  - Sakamoto, Yutaro
TI  - Hamilton Cycles in Double Generalized Petersen Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 117
EP  - 123
VL  - 39
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a9/
LA  - en
ID  - DMGT_2019_39_1_a9
ER  - 
%0 Journal Article
%A Sakamoto, Yutaro
%T Hamilton Cycles in Double Generalized Petersen Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 117-123
%V 39
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a9/
%G en
%F DMGT_2019_39_1_a9

[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] 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

[3] H.S.M. Coxeter, Self-dual configurations and regular graphs, Bull. Amer. Math. Soc. 56 (1950) 413-455. doi: 10.1090/S0002-9904-1950-09407-5

[4] X. Fu, Y. Yang and B. Jiang, On the domination number of generalized Petersen graphs P(n, 2), Discrete Math. 309 (2009) 2445-2451. doi: 10.1016/j.disc.2008.05.026

[5] R.M. Karp, Reducibility among combinatorial problems in: R.E. Miller and J.W. Thatcher (Eds.), (Plenum Press, New York, 1972) 85-103 doi: 10.1007/978-1-4684-2001-2 9.

[6] K. Kutnar and P. Petecki, On automorphisms and structural properties of double generalized Petersen graphs, Discrete Math. 339 (2016) 2861-2870. doi: 10.1016/j.disc.2016.05.032

[7] 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

[8] J.-X. Zhou and Y.-Q. Feng, Cubic vertex-transitive non-Cayley graphs of order 8p, Electron. J. Combin. 19 (2012) #P53.

[9] J.-X. Zhou and Y.-Q. Feng, Cubic bi-Cayley graphs over Abelian groups, European J. Combin. 36 (2014) 679-693. doi: 10.1016/j.ejc.2013.10.005.