pipette
ESEspañol

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

Jifu Lin, Heng Yang

Preprint

In the authors' words

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.

Main resultThe abstract does not state a limitation.

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

Authors' comment: 12 pages