Recognizing generalized Petersen graphs in linear time

DOI10.1016/J.DAM.2020.03.007MaRDI QIDQ2192132zbMATH OpenOpenAlexFDO

Authors Matjaž Krnc, Robin 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

linear algorithmsgeneralized Petersen graphsgraph recognition

Mathematics Subject Classification ID

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

Abstract: By identifying a local property which structurally classifies any edge, we show that the family of generalized Petersen graphs can be recognized in linear time.

Recommendations

• scientific article; zbMATH DE number 4049084
• Generalizing the generalized Petersen graphs
• On the neighbor-distinguishing in generalized Petersen graphs
• Recognizing near-bipartite Pfaffian graphs in polynomial time
• A new generalization of generalized Petersen graphs
• Linear recognition of pseudo-split graphs
• scientific article; zbMATH DE number 1203995
• Recognizing hyperelliptic graphs in polynomial time
• Recognizing hyperelliptic graphs in polynomial time
• scientific article; zbMATH DE number 4206028

Cites work

• scientific article; zbMATH DE number 227006 (Why is no real title available?)
• scientific article; zbMATH DE number 3349883 (Why is no real title available?)
• A note on the generalized Petersen graphs that are also Cayley graphs
• A result on Hamiltonian cycles in generalized Petersen graphs
• A theorem on tait colorings with an application to the generalized Petersen graphs
• Enumeration of I-graphs: Burnside does it again
• Equitable total coloring of generalized Petersen graphs \(P(n,k)\).
• Every generalized Petersen graph has a Tait coloring
• Generalized Petersen graphs and Kronecker covers
• Hamilton cycles in double generalized Petersen graphs
• Lower bound on the number of Hamiltonian cycles of generalized Petersen graphs
• On the minimum vertex cover of generalized Petersen graphs
• On the reliability of generalized Petersen graphs
• Partial cubes as subdivision graphs and as generalized Petersen graphs
• Self-dual configurations and regular graphs
• The classification of Hamiltonian generalized Petersen graphs
• The ubiquitous Petersen graph
• Variations on the Hamiltonian Theme
• Which generalized petersen graphs are cayley graphs?

Cited in

(3)

• Determining the edge metric dimension of the generalized Petersen graph \(P(n, 3)\)
• Recognizing Hamming graphs in linear time and space
• Distinguishing graphs via cycles

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

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