On Hamilton Cycles in 3-Connected Cubic Maps

L. Bruce Richmond, R. W. Robinson, N. C. Wormald

Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review

1 Citation (Scopus)

Abstract

We show that the probability of a 3-connected cubic map with 2n vertices being hamiltonian tends to zero exponentially with with n. We show that if there is one 3-connected triangulation which is not 4-colourable then the probability that a 3-connected triangulation is 4-colourable tends to zero exponentially with n. These results both follow easily from the result proved here that any given 3-connected triangulation, T, is contained (with the boundary of T an interior 3-cycle) in a 3-connected triangulation with 2n faces with probability 1 + 0(cn), c < 1.

Original languageEnglish
Title of host publicationAnnals of Discrete Mathematics (27)
Subtitle of host publicationCycles in Graphs
EditorsB.R. Alspach, C.D. Godsil
Place of PublicationNetherlands
Pages141-149
Number of pages9
Volume115
EditionC
DOIs
Publication statusPublished - 1 Jan 1985
Externally publishedYes

Publication series

NameNorth-Holland Mathematics Studies
ISSN (Print)0304-0208

Cite this