The path minimises the average size of a connected induced subgraph

Abstract

We prove that among all graphs of order n, the path uniquely minimises the average order of its connected induced subgraphs. This confirms a conjecture of Kroeker, Mol and Oellermann, and generalises a classical result of Jamison for trees, as well as giving a new, shorter proof of the latter. While this paper was being prepared, a different proof was given by Andrew Vince.

9 pages, 1 figure. Fixed a few typos

References in corpus (2)

• The number and average size of connected sets in graphs with degree constraints
• On the Mean Connected Induced Subgraph Order of Cographs

Cited by in corpus (2)

• The number and average size of connected sets in graphs with degree constraints
• Bounding mean orders of sub-$k$-trees of $k$-trees