2006/09/06 by Tibor Antal, T. Antal, P. L. Krapivsky
Mathematics · Physics and Astronomy · #Binary tree #Chordal graph #Combinatorics #Complex Network Analysis Techniques #Discrete mathematics #Distribution (mathematics) #Flow (mathematics) #Geometry #Graph #Mathematical analysis #Mathematics #Physics #Random graph #Root (linguistics) #Simple (philosophy) #Statistical physics #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.1103/physreve.74.051110
published as Physical Review E 74, 051110 (2006) · 8 pages, 6 figures
arxiv created 2006/09/06 · openalex publication_date 2006/11/13 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We investigate flows on graphs whose links have random capacities. For binary trees we derive the probability distribution for the maximal flow from the root to a leaf, and show that for infinite trees it vanishes beyond a certain threshold that depends on the distribution of capacities. We then examine the maximal total flux from the root to the leaves. Our methods generalize to simple graphs with loops, e.g., to hierarchical lattices and to complete graphs.