Recognizing generalized Petersen graphs in linear time

DOI10.1016/j.dam.2020.03.007zbMath1442.05122arXiv1701.05806OpenAlexW2580328797MaRDI QIDQ2192132

Matjaž Krnc, Robin J. Wilson

Publication date: 29 June 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

generalized Petersen graphslinear algorithmsgraph recognition

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (2)

Determining the edge metric dimension of the generalized Petersen graph \(P(n, 3)\) ⋮ Distinguishing graphs via cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The classification of Hamiltonian generalized Petersen graphs
• A result on Hamiltonian cycles in generalized Petersen graphs
• The ubiquitous Petersen graph
• A note on the generalized Petersen graphs that are also Cayley graphs
• On the reliability of generalized Petersen graphs
• Hamilton cycles in double generalized Petersen graphs
• Partial cubes as subdivision graphs and as generalized Petersen graphs
• On the minimum vertex cover of generalized Petersen graphs
• Lower bound on the number of Hamiltonian cycles of generalized Petersen graphs
• Every generalized Petersen graph has a Tait coloring
• Enumeration of I-graphs: Burnside does it again
• Which generalized petersen graphs are cayley graphs?
• A theorem on tait colorings with an application to the generalized Petersen graphs
• Variations on the Hamiltonian Theme
• Self-dual configurations and regular graphs

This page was built for publication: Recognizing generalized Petersen graphs in linear time