A lower bound on the average size of a connected vertex set of a graph

The topic is the average order of a connected induced subgraph of a graph. This generalizes, to graphs in general, the average order of a subtree of a tree. In 1983, Jamison proved that the average order of a subtree, over all trees of order n, is minimized by the path Pn. In 2018, Kroeker, Mol, and...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series B 2022-01, Vol.152, p.153-170
Main Author: Vince, Andrew
Format: Article
Language:English
Subjects:
Average order
Connectedness
Graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The topic is the average order of a connected induced subgraph of a graph. This generalizes, to graphs in general, the average order of a subtree of a tree. In 1983, Jamison proved that the average order of a subtree, over all trees of order n, is minimized by the path Pn. In 2018, Kroeker, Mol, and Oellermann conjectured that Pn minimizes the average order of a connected induced subgraph over all connected graphs. The main result of this paper confirms this conjecture.
ISSN:0095-8956
1096-0902
DOI:10.1016/j.jctb.2021.09.008