The External Path Length and Terminal Wiener Index in Random Trees

We consider two distance-based concepts in rooted trees and compare them to their leaf-restricted counterparts. The path length is the sum of all distances from the root to the vertices of the tree, while the external path length is the sum of all distances from the root to the leaves of the tree. Upon dividing by the number of vertices and leaves respectively, we obtain the average distance to the root. The Wiener index is the sum of all distances between pairs of vertices, and the terminal Wiener index is the sum of all distances between pairs of leaves. Dividing by the number of pairs of vertices and pairs of leaves respectively, we obtain the average distance between vertices and average distance between leaves. For two important classes of random trees, we show that the average distance of the root to a random leaf is almost the same as the average distance to a random vertex and that the average distance between vertices is almost the same as the average distance between leaves. For Bienaymé--Galton--Watson trees, each of these differences is bounded in probability. For three varieties of increasing trees (recursive trees, $d$-ary increasing trees, generalised plane-oriented recursive trees), on the other hand, the differences converge to constants in probability. This allows the transfer of convergence results for the path length to the external path length, and results for the Wiener index to be transferred to the terminal Wiener index.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-12
DOI
https://doi.org/10.48550/arxiv.2611.16674
Primary Topic
Graph theory and applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The External Path Length and Terminal Wiener Index in Random Trees

Jacob Lundblad, Stephan Wagner
arXiv (Cornell University)
Graph theory and applications
preprint

The External Path Length and Terminal Wiener Index in Random Trees

Jacob Lundblad, Stephan Wagner
preprint en

Abstract

We consider two distance-based concepts in rooted trees and compare them to their leaf-restricted counterparts. The path length is the sum of all distances from the root to the vertices of the tree, while the external path length is the sum of all distances from the root to the leaves of the tree. Upon dividing by the number of vertices and leaves respectively, we obtain the average distance to the root. The Wiener index is the sum of all distances between pairs of vertices, and the terminal Wiener index is the sum of all distances between pairs of leaves. Dividing by the number of pairs of vertices and pairs of leaves respectively, we obtain the average distance between vertices and average distance between leaves. For two important classes of random trees, we show that the average distance of the root to a random leaf is almost the same as the average distance to a random vertex and that the average distance between vertices is almost the same as the average distance between leaves. For Bienaymé--Galton--Watson trees, each of these differences is bounded in probability. For three varieties of increasing trees (recursive trees, $d$-ary increasing trees, generalised plane-oriented recursive trees), on the other hand, the differences converge to constants in probability. This allows the transfer of convergence results for the path length to the external path length, and results for the Wiener index to be transferred to the terminal Wiener index.

arXiv (Cornell University)
Graph theory and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon