Paperlane

no. 12 · Tuesday 10 November 2026

Average distance and maximum induced linear forest

Mathieu Bouchard and Alain Hertz

math.CO · 18 pp

Abstract

Let G be a connected graph of order n, let μ(G) denote its average distance, and let L(G) denote the maximum order of an induced linear forest of G, that is, of an induced subgraph whose components are chains. Hansen, Hertz, Kilani, Marcotte and Schindl conjectured that μ(G) {\le} L(G)/2, which can be written as 4W(G) {\le} L(G)n(n-1), where W(G) is the Wiener index of G. This inequality strengthens their bound μ(G) {\le} F(G)/2, where F(G) is the maximum order of an induced forest, as well as Chung's classical bound μ(G) {\le} α(G). In this paper we prove the conjecture for all connected graphs.

comments
This paper establishes a conjecture dating back to 2009. It is 18 pages long and contains 4 figures
fields
Combinatorics
pdf ↗ page arXiv:2611.12781 ↗