On Hamilton Cycles in 3-Connected Cubic Maps

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

Research output: Contribution to journalArticleResearchpeer-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
Pages (from-to)141-149
Number of pages9
JournalNorth-Holland Mathematics Studies
Volume115
Issue numberC
DOIs
Publication statusPublished - 1 Jan 1985
Externally publishedYes

Cite this

Richmond, L. Bruce ; Robinson, R. W. ; Wormald, N. C. / On Hamilton Cycles in 3-Connected Cubic Maps. In: North-Holland Mathematics Studies. 1985 ; Vol. 115, No. C. pp. 141-149.
@article{4f75bdbf648347e191bbf2349c0ffe25,
title = "On Hamilton Cycles in 3-Connected Cubic Maps",
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.",
author = "Richmond, {L. Bruce} and Robinson, {R. W.} and Wormald, {N. C.}",
year = "1985",
month = "1",
day = "1",
doi = "10.1016/S0304-0208(08)73003-2",
language = "English",
volume = "115",
pages = "141--149",
journal = "North-Holland Mathematics Studies",
issn = "0304-0208",
number = "C",

}

On Hamilton Cycles in 3-Connected Cubic Maps. / Richmond, L. Bruce; Robinson, R. W.; Wormald, N. C.

In: North-Holland Mathematics Studies, Vol. 115, No. C, 01.01.1985, p. 141-149.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - On Hamilton Cycles in 3-Connected Cubic Maps

AU - Richmond, L. Bruce

AU - Robinson, R. W.

AU - Wormald, N. C.

PY - 1985/1/1

Y1 - 1985/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77956925747&partnerID=8YFLogxK

U2 - 10.1016/S0304-0208(08)73003-2

DO - 10.1016/S0304-0208(08)73003-2

M3 - Article

VL - 115

SP - 141

EP - 149

JO - North-Holland Mathematics Studies

JF - North-Holland Mathematics Studies

SN - 0304-0208

IS - C

ER -