2025/11/06 by Harrison Hartle, P. L. Krapivsky, Hartle, Harrison +1
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Probability (math.PR) #Social and Information Networks (cs.SI) #Statistical Mechanics (cond-mat.stat-mech) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.2511.04085
openalex publication_date 2025/11/06 · openalex created_date 2025/11/08 · openalex updated_date 2026/07/28
Leaves, i.e., vertices of degree one, can play a significant role in graph structure, especially in sparsely connected settings in which leaves often constitute the largest fraction of vertices. We consider a leaf-based counterpart of the degree, namely, the leaf degree -- the number of leaves a vertex is connected to -- and the associated leaf degree distribution, analogous to the degree distribution. We determine the leaf degree distribution of random recursive trees (RRTs) and trees grown via a leaf-based preferential attachment mechanism that we introduce. The RRT leaf degree distribution decays factorially, in contrast with its purely geometric degree distribution. In the one-parameter leaf-based growth model, each new vertex attaches to an existing vertex with rate ℓ + a, where ℓ is the leaf degree of the existing vertex, and a > 0. The leaf degree distribution has a powerlaw tail when 0 < a < 1 and an exponential tail (with algebraic prefactor) for a > 1. The critical case of a = 1 has a leaf degree distribution with stretched exponential tail. We compute a variety of additional characteristics in these models and conjecture asymptotic equivalence of degree and leaf degree powerlaw tail exponent in the scale free regime. We highlight several avenues of possible extension for future studies.