Premium
Largest 4 ‐connected components of 3 ‐connected planar triangulations
Author(s) -
Bender Edward A.,
Richmond L. Bruce,
Wormald Nicholas C.
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240070402
Subject(s) - combinatorics , connected component , vertex (graph theory) , planar , triangulation , mathematics , planar graph , geometry , computer science , graph , computer graphics (images)
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) .
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom