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).
| Original language | English |
|---|---|
| Pages (from-to) | 273-285 |
| Number of pages | 13 |
| Journal | Random Structures & Algorithms |
| Volume | 7 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 1995 |
| Externally published | Yes |
Cite this
Bender, E. A., Richmond, L. B., & Wormald, N. C. (1995). Largest 4‐connected components of 3‐connected planar triangulations. Random Structures & Algorithms, 7(4), 273-285. https://doi.org/10.1002/rsa.3240070402