Abstract
It is known that there exists a cycle through any nine vertices of a 3-connected cubic graphG. Here we show that if an edge is removed from such a graph, then there is still a cycle through any five vertices. Furthermore, we characterise the circumstances in which there fails to be a cycle through six. As corollaries we are able to prove that a 3-connected cubic graph has a cycle through any specified five vertices and one edge, and to classify the conditions under which it has a cycle through four chosen vertices and two edges.
We are able to use the five and six vertex results to show that a 3-connected cubic graph has a cycle which passes through any ten given vertices if and only if the graph is not contractible to the Petersen graph in such a way that the ten vertices each map to a distinct vertex of the Petersen graph.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. A. Bondy andU. S. R. Murty,Graph Theory with Applications, Macmillan, London, 1976.
F. C. Bussemaker, S. Cobeljić, D. M. Cvetković andJ. J. Seidel, Computer investigation of cubic graphs,Technological University of Eindhoven, Mathematics Research Report WSK-01, 1976.
M. N. Ellingham, Constructing certain cubic graphs,Combinatorial Mathematics IX, Lecture Notes in Maths., No.952, Springer, Berlin, 1982, 252–274.
D. A. Holton, B. D. McKay, M. D. Plummer andC. Thomassen, A nine point theorem for 3-connected graphs,Combinatorica,2 (1982), 53–62.
A. K. Kelmans andM. V. Lomonosov, Whenm vertices in ak-connected graph cannot be walked round along a simple cycle,Discrete Math. 38 (1982), 317–322.
A. K. Kelmans andM. V. Lomonosov, A cubic 3-connected graph having no cycles through given 10 vertices has the “Petersen” form,Amer. Math. Soc. Abstracts, No. 82T-05-260,3 (1982), 283.