Nonhamiltonian 3-Connected Cubic Planar Graphs
Authors:
- R. E. L. AldredRAR. E. L. Aldred
- S. BauSBS. Bau
- D. A. HoltonDHD. A. Holton
- Brendan D. McKayBMBrendan D. McKay
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 13 (1) , 25-32
Abstract
We establish that every cyclically 4-connected cubic planar graph of order at most 40 is hamiltonian. Furthermore, this bound is determined to be sharp, and we present all nonhamiltonian examples of order 42. In addition we list all nonhamiltonian cyclically 5-connected cubic planar graphs of order at most 52 and all nonhamiltonian 3-connected cubic planar graphs of girth 5 on at most 46 vertices. The fact that all 3-connected cubic planar graphs on at most 176 vertices and with face size at most 6 are hamiltonian is also verified.Keywords
This publication has 7 references indexed in Scilit:
- PentHex PuzzlesAdvances in Applied Mathematics, 1998
- A Constructive Enumeration of FullerenesJournal of Algorithms, 1997
- ErratumJournal of Combinatorial Theory, Series B, 1989
- Every simple 3‐polytope of order 32 or less is HamiltonianJournal of Graph Theory, 1982
- Non-hamiltonian cubic planar mapsDiscrete Mathematics, 1974
- A Generation Procedure for the Simple 3-Polytopes With Cyclically 5-Connected GraphsCanadian Journal of Mathematics, 1974
- On generating planar graphsDiscrete Mathematics, 1974