Graphical sequences and plane trees

2024/06/07 by Michal Bassan, Serte Donderwinkel, Bassan, Michal +3
#05A15 #05A16 #05A17 #05C30 #11P21 #51M20 #52B05 #60E07 #60G50 #60K05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2406.05110

Abstract

Balister, the second author, Groenland, Johnston and Scott recently showed that there are asymptotically C4ⁿ/n^3/4 many unordered sequences that occur as degree sequences of graphs. Combining limit theory for infinitely divisible distributions with a new bijective connection between a class of random walk trajectories and a subset counting formula from additive number theory, we describe 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.

Related

• Counting graphic sequences via integrated random walks
• Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph
• On the limit of large girth graph sequences
• The number of graphs and a random graph with a given degree sequence
• An Improved Algorithm for Counting Graphical Degree Sequences