A sharp bound on the binding number of -free graphs and the Brandt conjecture
En palabras de los autores
The binding number of a graph is the smallest ratio among all nonempty vertex sets whose neighborhood is not the whole vertex set. We prove that every finite nonempty -free graph has binding number at most for every , confirming Brandt's conjecture; the bound is sharp for complete -partite graphs with equal nonempty parts. We first prove the case and then extend it to all by induction.
Resultado principalEl resumen no menciona limitaciones.
Apareció: miércoles, 21 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 12 pages