Graphical sequences and plane trees
Abstract
Abstract Balister, the second author, Groenland, Johnston, and Scott recently showed that there are asymptotically upper C 4 Superscript n divided by n Superscript 3 divided by 4 C 4 n / n 3 / 4 $C4^n/n^{3/4}$ many unordered sequences that occur as degree sequences of graphs with n n $n$ vertices. Combining limit theory for infinitely divisible distributions with a new connection between a class of random walk trajectories and a subset counting formula from additive number theory, we describe upper C C $C$ in terms of Walkup’s number of rooted plane trees. The bijection is related to an instance of the Lévy–Khintchine formula. Our main result complements a result of Stanley, that ordered graphical sequences are related to quasi-forests.
Fields of Study & Subjects
Graph theory and applications
Advanced Graph Theory Research
Graph Theory and Algorithms
Publication details
- Journal / source
- Combinatorics Probability Computing
- Publisher
- Cambridge University Press (CUP)
- Volume
- 35
- Issue
- 3
- Pages
- 316–328
- Publication date
- 5 February 2026
- Language
- EN