pipette
ENEnglish

A sharp bound on the binding number of -free graphs and the Brandt conjecture

Jifu Lin, Heng Yang

Preprint

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