Recognizing generalized Petersen graphs in linear time

DOI10.1016/J.DAM.2020.03.007zbMATH Open1442.05122arXiv1701.05806OpenAlexW2580328797MaRDI QIDQ2192132FDOQ2192132

Authors: Matjaž Krnc, Robin Wilson 

Publication date: 29 June 2020

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

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.

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

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

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)

Cites Work

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

Cited In (3)

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

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)