Paperlane

no. 15 · Monday 16 November 2026

Branching Ratios of Input Trees for Directed Multigraphs

Paolo Boldi and Ian Stewart

math.CO · v2 · 34 pp

Abstract

We define the branching ratio of the input tree of a node in a finite directed multigraph, prove that it exists for every node, and show that it is equal to the largest eigenvalue of the adjacency matrix of the induced subgraph determined by all upstream nodes. This real eigenvalue exists by the Perron-Frobenius Theorem for non-negative matrices. We motivate our analysis with simple examples, obtain information about the asymptotics for the limit growth of the input tree, and establish other basic properties of the branching ratio.

comments
34 pages, 10 figures
journal
Journal of Algebraic Combinatorics (2026)
fields
Combinatorics
pdf ↗ page arXiv:2501.06812 ↗