The number and average size of connected sets in graphs with degree constraints

Journal article

The average size of connected vertex subsets of a connected graph generalises a much-studied parameter for subtrees of trees. For trees, the possible values of this parameter are critically affected by the presence or absence of vertices of degree 2. We answer two questions of Andrew Vince regarding the effect of degree constraints on general connected graphs. We give a new lower bound, and the first nontrivial upper bound, on the maximum growth rate of the number of connected sets of a cubic graph, and in fact obtain nontrivial upper bounds for any constant bound on the maximum degree. We show that the average connected set density is bounded away from 1 for graphs with no vertex of degree 2, and generalise a classical result of Jamison for trees by showing that in order for the connected set density to approach 1, the proportion of vertices of degree 2 must approach 1. Finally, we show that any sequence of graphs with minimum degree tending to infinity must have connected set density tending to 1/2.

Authors: Haslegrave, JGE

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Wiley
• Journal: Journal of Graph Theory
• Volume: 100
• Issue: 3
• Pages: 530-542
• Publication date: 2022-01-12
• Acceptance date: 2021-12-23
• DOI: 10.1002/jgt.22793
• EISSN: 1097-0118
• ISSN: 0364-9024
• Language: English
• Keywords: connected graph; extremal graph theory; connected induced subgraph; average graph parameter; FFR