Graphical sequences and plane trees

doi:10.1017/S0963548325100345

Graphical sequences and plane trees

2026-02-01

0

OA

AI

DOI：10.1017/S0963548325100345

Original

Original request for help

Save

Abstract

En 中文

Balister, the second author, Groenland, Johnston, and Scott recently showed that there are asymptotically $C4<^>n/n<^>{3/4}$ many unordered sequences that occur as degree sequences of graphs with $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 $C$ in terms of Walkup's number of rooted plane trees. The bijection is related to an instance of the L & eacute;vy-Khintchine formula. Our main result complements a result of Stanley, that ordered graphical sequences are related to quasi-forests.

Keywords:

asymptotic enumeration

degree sequence

graphical sequence

infinite divisibility

L & eacute

vy-Khintchine formula

random walk

renewal theory

Graphical sequences and plane trees

Abstract

Journal

Organization