Abstract
We prove that a 3-connected cubic graph contains a cycle through any nine points.
Similar content being viewed by others
References
A. T. Balaban, R. O. Davies, F. Harary, A. Hill andR. Westwick, Cubic identity graphs derived from trees,J. Austral. Math. Soc.,11 (1970), 207–215.
J. A. Bondy andL. Lovász, Cycles through specified vertices of a graph,Combinatorica 1 (2) (1981), 117–140.
J. A. Bondy andU. S. R. Murty,Graph Theory with Applications, MacMillan, London, 1976.
F. C. Busemaker, S. Cobeljić, D. M. Cvetković andJ. J. Seidel, Computer investigation of cubic graphs,Technological University of Edindhoven, Mathematics Research Report WSK-01, 1976.
V. Chvátal, Flip-flops in hypohamiltonian graphs,Canad. Math. Bull.,16 (1973), 33–41.
G. A. Dirac, In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen,Math. Nachr.,22 (1960), 61–85.
R. Häggkvist andC. Thomassen, Circuits through specified edges,Discrete Math., to appear.
D. A. Holton, Cycles through specified vertices ink-connected regular graphs,preprint 1980.
L. Lovász, Problem 5,Per. Math. Hungar.,4 (1974), 82.
G. H. J. Meredith, Regularn-valentn-connected non-hamiltonian non-n-edge-colorable graphs,J. Combinatorial Th., B.,14 (1973), 55–60.
C. Thomassen, Planar cubic hypohamiltonian and hypotraceable graphs,J. Combinatorial Th. B.,30 (1981), 36–44.
M. E. Watkins andD. M. Mesner, Cycles and connectivity in graphs,Canad. J. Math.,19 (1967), 1319–1328.
D. R. Woodall, Circuits containing specified edges,J. Combinatorial Th. B.,22 (1977), 274–278.
Author information
Authors and Affiliations
Additional information
This author is grateful for support from the Sonderforschungsbereich 21 (DFG), Institut für Ökonometrie und Operations Research, Universität Bonn, the University of Melbourne and the Vanderbilt University Research Council during the preparation of this paper.
Rights and permissions
About this article
Cite this article
Holton, D.A., McKay, B.D., Plummer, M.D. et al. A nine point theorem for 3-connected graphs. Combinatorica 2, 53–62 (1982). https://doi.org/10.1007/BF02579281
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02579281