The path minimises the average size of a connected induced subgraph

DOI10.1016/J.DISC.2022.112799MaRDI QIDQ2113349zbMATH OpenOpenAlexFDO

Authors John Haslegrave

Publication date 14 March 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2103.16491

zbMATH Keywords

connected graphextremal graph theoryaverage graph parameterconnected induced subgraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial probability (60C05) Paths and cycles (05C38) Connectivity (05C40)

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.

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

Cites work

• scientific article; zbMATH DE number 3849252 (Why is no real title available?)
• A lower bound on the average size of a connected vertex set of a graph
• Extremal results on average subtree density of series-reduced trees
• On the average number of nodes in a subtree of a tree
• On the mean connected induced subgraph order of cographs
• On the mean order of connected induced subgraphs of block graphs
• Subtrees of graphs
• The average order of a subtree of a tree
• The average size of a connected vertex set of a graph—Explicit formulas and open problems

Cited in

(6)

• 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 connected induced subgraph order of cographs
• On the mean order of connected induced subgraphs of block graphs
• A tight upper bound on the average order of dominating sets of a graph
• On the local and global mean orders of sub-\(k\)-trees of \(k\)-trees

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)