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

DOI10.1016/J.JCTB.2021.09.008MaRDI QIDQ2664553zbMATH OpenOpenAlexFDO

Authors Andrew Vince

Publication date 17 November 2021

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

average ordergraph connectedness

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: 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 1984, Jamison proved that the average order, over all trees of order $n$, is minimized by the path $P_n$. In 2018, Kroeker, Mol, and Oellermann conjectured that $P_n$ minimizes the average order over all connected graphs. The main result of this paper confirms this conjecture.

Recommendations

• The average size of a connected vertex set of a \(k\)-connected graph
• The path minimises the average size of a connected induced subgraph
• 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
• The average order of a subtree of a tree

Cites work

• Enumeration of subtrees of trees
• Extremal results on average subtree density of series-reduced trees
• Graphs of maximum diameter
• Maximizing the mean subtree order
• Monotonicity of the mean order of subtrees
• On the average number of nodes in a subtree of a tree
• On the local and global means of subtree orders
• On the mean connected induced subgraph order of cographs
• On the mean order of connected induced subgraphs of block 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
• The mean order of sub-\(k\)-trees of \(k\)-trees
• The number and average size of connected sets in graphs with degree constraints

Cited in

(17)

• Bounds on the average connectivity of a graph
• The average size of a connected vertex set of a \(k\)-connected graph
• The path minimises the average size of a connected induced subgraph
• On the local and global mean orders of sub-k-trees of k-trees
• Extremal results on average subtree density of series-reduced trees
• On the mean connected induced subgraph order of cographs
• On the Average (Edge-)Connectivity of Minimally k-(Edge-)Connected Graphs
• On the mean order of connected induced subgraphs of block graphs
• On the mean subtree order of trees under edge contraction
• The average size of a connected vertex set of a graph—Explicit formulas and open problems
• The number and average size of connected sets in graphs with degree constraints
• Solution to a conjecture on the mean subtree order of graphs under edge addition
• Computing the number and average size of connected sets in planar 3-trees
• A tight upper bound on the average order of dominating sets of a graph
• The average order of a connected vertex set in generalized ladder graphs
• The average order of a connected induced subgraph of a graph and union-intersection systems
• Lower bound of the Hadwiger number of graphs by their average degree

This page was built for publication: A lower bound on the average size of a connected vertex set of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2664553)