The path minimises the average size of a connected induced subgraph

DOI10.1016/j.disc.2022.112799zbMath1484.05110arXiv2103.16491OpenAlexW3209475899MaRDI QIDQ2113349

John Haslegrave

Publication date: 14 March 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

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) Paths and cycles (05C38) Combinatorial probability (60C05) Connectivity (05C40)

Related Items (1)

On the local and global mean orders of sub-\(k\)-trees of \(k\)-trees

Cites Work

• Extremal results on average subtree density of series-reduced trees
• The average order of a subtree of a tree
• On the average number of nodes in a subtree of a tree
• A lower bound on the average size of a connected vertex set of a graph
• On the Mean Connected Induced Subgraph Order of Cographs
• Subtrees of graphs
• 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
• Unnamed Item

This page was built for publication: The path minimises the average size of a connected induced subgraph