Journal article icon

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


Publisher copy:
10.1016/j.disc.2022.112799

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Role:
Author
Publisher:
Elsevier Publisher's website
Journal:
Discrete Mathematics Journal website
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

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP