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 and Algorithms |
Volume | 7 |
Issue number | 4 |
DOIs | |
Publication status | Published - 1995 |
Externally published | Yes |