Counting connected multitype graphs with prescribed edge counts
Abstract
We determine the exponential asymptotics of the number of connected labelled graphs with finitely many vertex types, prescribed numbers of vertices of each type, and prescribed edge counts between each pair of types. Under an irreducibility and strict surplus condition, we express the count for linear surplus of edges as the unrestricted count multiplied by an explicit exponential connectivity factor, up to a multiplicative error exp{o(n)}. The factor is characterized by a finite-dimensional nonlinear system whose solution exists and is unique. We use a probabilistic method, exploiting large-deviation principles and asymptotic estimates for connectedness probabilities to relate the counting problem to the emergence of giant components in suitably tuned supercritical random graphs. For connected bipartite graphs, we determine the exponential rate throughout the regime of positive linear excess and fixed positive limiting proportions of the two vertex classes. In the parameter ranges where the existing upper and lower bounds apply, this identifies the exponential rate left undetermined by those estimates.
Related
- Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
- The maximum spectral radius of connected graphs with prescribed order and size
- Counting Nilpotent Galois extensions with prescribed genus number
- Counting subspaces with prescribed Welch sums
- Counting t-wise L-intersecting cliques with prescribed intersection sizes
BibTeX
@misc{andreis2026counting,
title = {{Counting connected multitype graphs with prescribed edge counts}},
author = {Luisa Andreis and Mario Veshaj},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.17912},
eprint = {2606.17912},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.17912},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Counting connected multitype graphs with prescribed edge counts
AU - Luisa Andreis
AU - Mario Veshaj
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2606.17912
UR - https://arxiv.org/abs/2606.17912
AB - We determine the exponential asymptotics of the number of connected labelled graphs with finitely many vertex types, prescribed numbers of vertices of each type, and prescribed edge counts between each pair of types. Under an irreducibility and strict surplus condition, we express the count for linear surplus of edges as the unrestricted count multiplied by an explicit exponential connectivity factor, up to a multiplicative error exp{o(n)}. The factor is characterized by a finite-dimensional nonlinear system whose solution exists and is unique. We use a probabilistic method, exploiting large-deviation principles and asymptotic estimates for connectedness probabilities to relate the counting problem to the emergence of giant components in suitably tuned supercritical random graphs. For connected bipartite graphs, we determine the exponential rate throughout the regime of positive linear excess and fixed positive limiting proportions of the two vertex classes. In the parameter ranges where the existing upper and lower bounds apply, this identifies the exponential rate left undetermined by those estimates.
ER -