Journal article
The path minimises the average size of a connected induced subgraph
- Abstract:
-
We prove that among connected graphs of order n, the path uniquely minimises the average order of its connected induced subgraphs. This confirms a conjecture of Kroeker, Mol and Oellermann, and generalises a classical result of Jamison for trees, as well as giving a new, shorter proof of the latter.
A different proof of the main result was given independently and almost simultaneously by Andrew Vince; the two preprints were submitted one day apart.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 270.8KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.disc.2022.112799
Authors
- Publisher:
- Elsevier
- Journal:
- Discrete Mathematics More from this journal
- Volume:
- 345
- Issue:
- 5
- Article number:
- 112799
- Publication date:
- 2022-01-20
- Acceptance date:
- 2022-01-05
- DOI:
- ISSN:
-
0012-365X
- Language:
-
English
- Keywords:
- Pubs id:
-
1237437
- Local pid:
-
pubs:1237437
- Deposit date:
-
2022-02-04
- ARK identifier:
Terms of use
- Copyright holder:
- John Haslegrave
- Copyright date:
- 2022
- Rights statement:
- © 2022 The Author. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record