The average size of a connected vertex set of a k-connected graph

DOI10.1016/J.DISC.2021.112523MaRDI QIDQ2043391zbMATH OpenOpenAlexFDO

Authors Andrew Vince

Publication date 2 August 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

average orderconnectedness

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Connectivity (05C40)

Abstract: The topic is the average order $A(G)$ of a connected induced subgraph of a graph $G$. 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$, the average being $A(P_n)=(n+2)/3$. In 2018, Kroeker, Mol, and Oellermann conjectured that $P_n$ minimizes the average order over all connected graphs $G$ - a conjecture that was recently proved. In this short note we show that this lower bound can be improved if the connectivity of $G$ is known. If $G$ is $k$-connected, then [A(G) geq frac{n}2 Bigg (1- frac{1}{2^k+1} Bigg ).]

Recommendations

• A lower bound on the average size of a connected vertex set of a graph
• The path minimises the average size of a connected induced subgraph
• On the Average (Edge-)Connectivity of Minimally k-(Edge-)Connected Graphs
• On the mean order of connected induced subgraphs of block graphs
• The average connectivity of a graph

Cites work

• A lower bound on the average size of a connected vertex set of a graph
• Enumeration of subtrees of trees
• Extremal results on average subtree density of series-reduced trees
• 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

Cited in

(13)

• The average connectivity of a graph
• The average connectivity of a digraph
• The path minimises the average size of a connected induced subgraph
• The average size of independent sets of graphs
• A lower bound on the average size of a connected vertex set of a graph
• On the local and global mean orders of sub-k-trees of k-trees
• On the Average (Edge-)Connectivity of Minimally k-(Edge-)Connected 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
• Extremal graphs for average sizes of maximal matchings
• The number and average size of connected sets in graphs with degree constraints
• On average sizes and enumeration of minimal edge covers
• The average order of a connected induced subgraph of a graph and union-intersection systems

This page was built for publication: The average size of a connected vertex set of a \(k\)-connected graph

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