Graphical sequences and plane trees

Journal article

Balister, the second author, Groenland, Johnston, and Scott recently showed that there are asymptotically many unordered sequences that occur as degree sequences of graphs with 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 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.

Authors: Bassan, M; Donderwinkel, S; Kolesnik, B

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Cambridge University Press
• Journal: Combinatorics, Probability and Computing
• Pages: 1-13
• Publication date: 2026-02-05
• Acceptance date: 2025-11-24
• DOI: 10.1017/s0963548325100345
• EISSN: 1469-2163
• ISSN: 0963-5483
• Language: English
• Keywords: 05A17; random walk; 60G50; 05C30; 52B05; infinite divisibility; renewal theory; asymptotic enumeration; 60E07; 05A15; 60K05; degree sequence; 05A16; 11P21; 51M20; Lévy–Khintchine formula; graphical sequence