The path minimises the average size of a connected induced subgraph
From MaRDI portal
Publication:2113349
DOI10.1016/J.DISC.2022.112799zbMATH Open1484.05110arXiv2103.16491OpenAlexW3209475899MaRDI QIDQ2113349FDOQ2113349
Authors: John Haslegrave 
Publication date: 14 March 2022
Published in: Discrete Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/2103.16491
Recommendations
- A lower bound on the average size of a connected vertex set of a graph
- The average size of a connected vertex set of a \(k\)-connected graph
- On the mean order of connected induced subgraphs of block graphs
- The average size of a connected vertex set of a graph—Explicit formulas and open problems
- On the mean connected induced subgraph order of cographs
Extremal problems in graph theory (05C35) Combinatorial probability (60C05) Paths and cycles (05C38) Connectivity (05C40)
Cites Work
- On the average number of nodes in a subtree of a tree
- Title not available (Why is that?)
- Extremal results on average subtree density of series-reduced trees
- The average order of a subtree of a tree
- A lower bound on the average size of a connected vertex set of a graph
- Subtrees of graphs
- On the Mean Connected Induced Subgraph Order of Cographs
- On the Mean Order of Connected Induced Subgraphs of Block Graphs
- The average size of a connected vertex set of a graph—Explicit formulas and open problems
Cited In (2)
This page was built for publication: The path minimises the average size of a connected induced subgraph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2113349)
