The Library
The number and average size of connected sets in graphs with degree constraints
Tools
Tools
Tools
Haslegrave, John (2022) The number and average size of connected sets in graphs with degree constraints. Journal of Graph Theory, 100 (3). pp. 530-542. doi:10.1002/jgt.22793 ISSN 0364-9024.
|
PDF
WRAP-number-average-size-connected-sets-graphs-degree-constraints-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (487Kb) | Preview |
Official URL: https://doi.org/10.1002/jgt.22793
Abstract
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.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
| SWORD Depositor: | Library Publications Router | ||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory | ||||||||
| Journal or Publication Title: | Journal of Graph Theory | ||||||||
| Publisher: | John Wiley & Sons Ltd. | ||||||||
| ISSN: | 0364-9024 | ||||||||
| Official Date: | July 2022 | ||||||||
| Dates: |
|
||||||||
| Volume: | 100 | ||||||||
| Number: | 3 | ||||||||
| Page Range: | pp. 530-542 | ||||||||
| DOI: | 10.1002/jgt.22793 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||
| Date of first compliant deposit: | 3 March 2022 | ||||||||
| Date of first compliant Open Access: | 3 March 2022 | ||||||||
| RIOXX Funder/Project Grant: |
|
||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
