The number and structure of connected graphs with a fixed degree sequence
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914545071554560 |
|---|---|
| author | Bell, Sasha Donderwinkel, Serte van der Hofstad, Remco |
| author_facet | Bell, Sasha Donderwinkel, Serte van der Hofstad, Remco |
| contents | We study connected graphs with a fixed degree sequence, in the sparse setting where the number of edges grows linearly in the number of vertices. Using the relation to the configuration model, we identify the number of such connected graphs up to the exponential order. We do this by viewing a connected graph with a given degree distribution as the realization of the giant component in a larger configuration model, and carefully choosing the degree distribution of the larger graph so that it is likely that its giant component has the required degree distribution. To ensure that the connected graph has exactly the correct degrees, we use a switching argument. Additionally, we obtain results on rare event probabilities and describe the local structure of a uniform connected graph with a fixed degree sequence. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_07923 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The number and structure of connected graphs with a fixed degree sequence Bell, Sasha Donderwinkel, Serte van der Hofstad, Remco Combinatorics Probability 05C30, 05C40, 60C05, 05C80 We study connected graphs with a fixed degree sequence, in the sparse setting where the number of edges grows linearly in the number of vertices. Using the relation to the configuration model, we identify the number of such connected graphs up to the exponential order. We do this by viewing a connected graph with a given degree distribution as the realization of the giant component in a larger configuration model, and carefully choosing the degree distribution of the larger graph so that it is likely that its giant component has the required degree distribution. To ensure that the connected graph has exactly the correct degrees, we use a switching argument. Additionally, we obtain results on rare event probabilities and describe the local structure of a uniform connected graph with a fixed degree sequence. |
| title | The number and structure of connected graphs with a fixed degree sequence |
| topic | Combinatorics Probability 05C30, 05C40, 60C05, 05C80 |
| url | https://arxiv.org/abs/2605.07923 |