Largest 4‐connected components of 3‐connected planar triangulations

Edward A. Bender; L. Bruce Richmond; Nicholas C. Wormald

doi:10.1002/rsa.3240070402

Largest 4‐connected components of 3‐connected planar triangulations

Edward A. Bender, L. Bruce Richmond, Nicholas C. Wormald

Research output: Contribution to journal › Article › Research › peer-review

9 Citations (Scopus)

Abstract

Let T_n be a 3‐connected n‐vertex planar triangulation chosen uniformly at random. Then the number of vertices in the largest 4‐connected component of T_n is asymptotic to n/2 with probability tending to 1 as n → ∞. It follows that almost all 3‐connected triangulations with n vertices have a cycle of length at least n/2 + o(n).

Original language	English
Pages (from-to)	273-285
Number of pages	13
Journal	Random Structures and Algorithms
Volume	7
Issue number	4
DOIs	https://doi.org/10.1002/rsa.3240070402
Publication status	Published - 1995
Externally published	Yes

Access to Document

10.1002/rsa.3240070402

Cite this

@article{17f3d74e8d07409e9b9abfd7d8038e82,

title = "Largest 4‐connected components of 3‐connected planar triangulations",

abstract = "Let Tn be a 3‐connected n‐vertex planar triangulation chosen uniformly at random. Then the number of vertices in the largest 4‐connected component of Tn is asymptotic to n/2 with probability tending to 1 as n → ∞. It follows that almost all 3‐connected triangulations with n vertices have a cycle of length at least n/2 + o(n).",

author = "Bender, {Edward A.} and Richmond, {L. Bruce} and Wormald, {Nicholas C.}",

year = "1995",

doi = "10.1002/rsa.3240070402",

language = "English",

volume = "7",

pages = "273--285",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley & Sons",

number = "4",

}

TY - JOUR

T1 - Largest 4‐connected components of 3‐connected planar triangulations

AU - Bender, Edward A.

AU - Richmond, L. Bruce

AU - Wormald, Nicholas C.

PY - 1995

Y1 - 1995

N2 - Let Tn be a 3‐connected n‐vertex planar triangulation chosen uniformly at random. Then the number of vertices in the largest 4‐connected component of Tn is asymptotic to n/2 with probability tending to 1 as n → ∞. It follows that almost all 3‐connected triangulations with n vertices have a cycle of length at least n/2 + o(n).

AB - Let Tn be a 3‐connected n‐vertex planar triangulation chosen uniformly at random. Then the number of vertices in the largest 4‐connected component of Tn is asymptotic to n/2 with probability tending to 1 as n → ∞. It follows that almost all 3‐connected triangulations with n vertices have a cycle of length at least n/2 + o(n).

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

U2 - 10.1002/rsa.3240070402

DO - 10.1002/rsa.3240070402

M3 - Article

AN - SCOPUS:84990706258

VL - 7

SP - 273

EP - 285

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 4

ER -

Largest 4‐connected components of 3‐connected planar triangulations

Abstract

Access to Document

Other files and links

Cite this