pipette
ESEspañol

A proof of Vince's conjecture on the average order of connected induced subgraphs

Jungang Chen, Hongxia Ma

Preprint

In the authors' words

We prove that the average order of connected induced subgraphs of a connected simple graph of order and minimum degree at least is strictly greater than , which settles a conjecture of Vince~[\emph{J. Graph Theory} 97 (2021), 82--103]. We go further and show that, for connected simple graphs of order and minimum degree exactly , uniquely minimizes this average under additional conditions.

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.