The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices (Q1085184)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices |
scientific article |
Statements
The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices (English)
0 references
1988
0 references
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.
0 references
cubic planar graphs
0 references
convex polytope
0 references
simplex polytope
0 references
Hamiltonian cycle
0 references
non-Hamiltonian graph
0 references
