A proof of Vince's conjecture on the average order of connected induced subgraphs
En palabras de los autores
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.
Resultado principalEl resumen no menciona limitaciones.
Apareció: miércoles, 21 de octubre. arXiv. Preprint, todavía sin revisión por pares.