On a conjecture concerning the Petersen graph

Publication date 17 February 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/231282, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p20.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Petersen graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40) Structural characterization of families of graphs (05C75)

Review text

Robertson has conjectured that the only 3-connected, internally 4-connected graph of girth 5 in which every odd cycle of length greater than 5 has a chord is the Petersen graph. The authors prove this conjecture in the special case where the graphs involved are also cubic. Moreover, this proof does not require the internal-4-connectivity assumption. An example is then presented to show that the assumption of internal 4-connectivity cannot be dropped as an hypothesis in the original conjecture. For an overview of the Petersen graph see [\textit{D. A. Holton} and \textit{J. Sheehan}, ``The Petersen graph, Australian Mathematical Society Lecture Series. 7. Cambridge: Cambridge University Press. (1993; Zbl 0781.05001)]). One of the main tools used in proving is the theorem of Mader that every graph, except the Petersen graph, of order \(n \geq 6\) with at least \(2n-5\) edges, and of girth at least 5 contains a subdivision of the complete graph on five vertices minus one edge. (See [\textit{W. Mader}, ``An extremal problem for subdivisions of \(K_5^-\), J. Graph Theory 30, No.\,4, 261--276 (1999; Zbl 0920.05040)].)

Recommendations

Cited in

(17)

This page was built for publication: On a conjecture concerning the Petersen graph

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