The maximum degree of planar graphs I. Series-parallel graphs
Michael DrmotaOmer GimenezMarc Noy
所有作者
Michael DrmotaOmer GimenezMarc Noy
文献摘要
We prove that the maximum degree Δn of a random series-parallel graph
with n vertices satisfies Δn/logn→c in probability, and
EΔn∼clogn for a computable constant c>0. The same
result holds for outerplanar graphs.