Hamilton cycles in double generalized Petersen graphs

DOI10.7151/DMGT.2062MaRDI QIDQ1630928zbMATH OpenOpenAlexFDO

Authors Yutaro Sakamoto

Publication date 5 December 2018

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1610.02212

zbMATH Keywords

double generalized Petersen graphHamilton cycle

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Abstract: Watkins (1969) first introduced the generalized Petersen graphs (GPGs) by modifying Petersen graph. Zhou and Feng (2012) modified GPGs and introduced the double generalized Petersen graphs (DGPGs). Kutnar and Petecki (2016) proved that DGPGs are Hamiltonian in special cases and conjectured that all DGPGs are Hamiltonian. In this paper, we construct Hamilton cycles in all DGPGs.

Recommendations

• Publication:4863464
• scientific article; zbMATH DE number 617579
• On the Hamilton laceability of double generalized Petersen graphs
• scientific article; zbMATH DE number 2024083
• All double generalized Petersen graphs are Hamiltonian
• Cycle double covers of graphs with Hamilton paths
• Enumeration of Hamiltonian cycles in certain generalized Petersen graphs
• Hyper-Hamiltonian generalized Petersen graphs
• Hamilton paths in generalized Petersen graphs
• scientific article; zbMATH DE number 841641

Cites work

• A theorem on tait colorings with an application to the generalized Petersen graphs
• Cubic bi-Cayley graphs over abelian groups
• Cubic vertex-transitive non-Cayley graphs of order 8p
• Every generalized Petersen graph has a Tait coloring
• On automorphisms and structural properties of double generalized Petersen graphs
• On the domination number of generalized petersen graphs \(P(n,2)\)
• Reducibility among combinatorial problems
• Self-dual configurations and regular graphs
• The classification of Hamiltonian generalized Petersen graphs

Cited in

(7)

• Recognizing generalized Petersen graphs in linear time
• Lower bound on the number of Hamiltonian cycles of generalized Petersen graphs
• All double generalized Petersen graphs are Hamiltonian
• Distinguishing graphs via cycles
• scientific article; zbMATH DE number 3961648 (Why is no real title available?)
• Double coverings of 2‐paths by Hamilton cycles*
• On automorphisms and structural properties of double generalized Petersen graphs

This page was built for publication: Hamilton cycles in double generalized Petersen graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1630928)