The ubiquitous Petersen graph
type: Item
instance of: scholarly article
title: The ubiquitous Petersen graph
zbMATH Open document ID: 0778.05070
DOI: 10.1016/0012-365X(92)90649-Z
author: Gary Chartrand
author: Héctor Hevia
author: Robin Wilson
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: This paper is an overview of recent results concerning the characterization of the well-known Petersen graph, or other results where this remarkable graph props up. A small selection of these follows: Petersen's graph is the smallest graph in which for any three distinct vertices there is another vertex adjacent to the first but not to the others. Except for Petersen's graph, every 2-connected graph with a least minimum degree 3 contains a cycle of length \(1\pmod 3\). Petersen's graph is the only non-Hamiltonian 2-connected \(k\)-regular graph of order \(2k+3\) or \(2k+4\) \((k>1)\). If \(G\) is a triangle-free graph, the largest bipartite subgraph of which contains exactly 4/5 of the edges of \(G\), then \(G\) is either Petersen's graph or the edge-graph of the dodecahedron.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 90266
zbMATH Keywords: Hamiltonian
zbMATH Keywords: characterization
zbMATH Keywords: Petersen graph
zbMATH Keywords: cycle
reviewed by: Frank Plastria
MaRDI profile type: Publication
cites work: Q3768931
cites work: Q3781781
cites work: An 11-vertex theorem for 3-connected cubic graphs
cites work: The classification of Hamiltonian generalized Petersen graphs
cites work: Q3801583
cites work: The Chvátal-Erdős condition and pancyclic line-graphs
cites work: Q3866156
cites work: Über Hamiltonsche Kreise und unabhängige Ecken in Graphen
cites work: Largest bipartite subgraphs in triangle-free graphs with maximum degree three
cites work: A generalization of Ore's Theorem involving neighborhood unions
cites work: Double cycle covers and the petersen graph
cites work: Q5284008
cites work: Q4343047
cites work: Q3216702
cites work: A note on Hamiltonian circuits
cites work: Minimalk-saturated and color critical graphs of prescribed minimum degree
cites work: Cycles through ten vertices in 3-connected cubic graphs
cites work: Q4121920
cites work: A class of Hamiltonian regular graphs
cites work: The smallest graphs with certain adjacency properties
cites work: A Ramsey-type theorem for traceable graphs
cites work: A nine point theorem for 3-connected graphs
cites work: Extremal bipartite subgraphs of cubic triangle-free graphs
cites work: Hamilton cycles in regular 2-connected graphs
cites work: A cubic 3-connected graph having no cycle through given 10 vertices has the “Petersen form”
cites work: Reduced graphs of diameter two
cites work: Q5653952
cites work: Hamiltonian paths in vertex-symmetric graphs of order 5p
cites work: On Critical Graphs of Diameter 2
cites work: Q3222222
cites work: Q4726284
description: scientific article; zbMATH DE number 90266