×

zbMATH — the first resource for mathematics

The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices. (English) Zbl 0607.05051
We show that all 3-connected cubic planar graphs on 36 or fewer vertices are hamiltonian, thus extending results of Lederberg, Butler, Goodey, Wegner, Okamura and Barnette. Furthermore, the only non-hamiltonian examples on 38 vertices which are not cyclically 4-connected are the six graphs which have been found by Lederberg, Barnette and Bosák.

MSC:
05C45 Eulerian and Hamiltonian graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
51M25 Length, area and volume in real or complex geometry
52Bxx Polytopes and polyhedra
Software:
nauty
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barnette, D, Every simple 3-polytope with 34 vertices in Hamiltonian, Discrete math., 162, 1-20, (1986) · Zbl 0602.05045
[2] Barnette, D; Wegner, G, Hamiltonian circuits in simple 3-polytopes with up to 26 vertices, Israel J. math., 19, 212-216, (1974) · Zbl 0302.05102
[3] Bosák, J, Hamiltonian lines in cubic graphs, (), 33-46 · Zbl 0183.52302
[4] {\scJ. Bosák}, private communication to B. Grünbaum (1971).
[5] Butler, J.W, Hamiltonian circuits on simple 3-polytopes, J. combin. theory ser. B, 15, 69-73, (1973) · Zbl 0248.05103
[6] Butler, J.W, Non-Hamiltonian simple 3-polytopes, (), 135-151
[7] Faulkner, G.B; Younger, D.H, Non-Hamiltonian cubic planar maps, Discrete math., 7, 67-74, (1974) · Zbl 0271.05106
[8] Goodey, P.R, Hamiltonian circuits on simple 3-polytopes, J. London math. soc. (2), 5, 504-510, (1972) · Zbl 0242.05137
[9] Grünbaum, B, ()
[10] Grünbaum, B, Polytopes, graphs and complexes, Bull. amer. math. soc., 76, 1131-1201, (1970) · Zbl 0211.25001
[11] Holton, D.A; McKay, B.D, (), Report 7
[12] Lederberg, J, Hamiltonian circuits on convex trivalent polyhedra (up to 18 vertices), Amer. math. monthly, 74, 522-527, (1967) · Zbl 0147.42702
[13] McKay, B.D, (), Tech. Report TR-CS-84-05
[14] Mohar, B, Search for minimal non-Hamiltonian simple 3-polytopes, (), 191-208, Novi Sad
[15] Okamura, H, Hamiltonian circuits on simple 3-polytopes with up to 30 vertices, J. math. soc. Japan, 34, 365-369, (1982) · Zbl 0481.05041
[16] Okamura, H, Every simple 3-polytope of order 32 or less is Hamiltonian, J. graph theory, 6, 185-196, (1982) · Zbl 0493.05043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.