The path minimises the average size of a connected induced subgraph |
| |
Institution: | Mathematical Institute, University of Oxford, UK |
| |
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. |
| |
Keywords: | Connected graph Extremal graph theory Connected induced subgraph Average graph parameter |
本文献已被 ScienceDirect 等数据库收录! |
|