Pendant appearances and components in random graphs from structured classes

2021/08/16 by Colin McDiarmid, McDiarmid, Colin
Computer Science · Mathematics · #05C80 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2108.07051

openalex publication_date 2021/08/16 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28

Abstract

We consider random graphs sampled uniformly from a structured class of graphs, such as the class of graphs embeddable in a given surface. We sharpen and extend earlier results on pendant appearances, concerning for example numbers of leaves; and obtain results on the asymptotic distribution of components other than the giant component, under quite general conditions.

Related

• Random graphs from structured classes
• Random graphs from a weighted minor-closed class
• Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
• Large-scale structures in random graphs
• Connectivity for random graphs from a weighted bridge-addable class