PreprintarXiv licencearXiv
A sharp bound on the binding number of Kk-free graphs and the Brandt conjecture
Abstract
The binding number of a graph is the smallest ratio $|N(S)|/|S|$ among all nonempty vertex sets S whose neighborhood N(S) is not the whole vertex set. We prove that every finite nonempty Kk-free graph has binding number at most k−2 for every k≥6, confirming Brandt's conjecture; the bound is sharp for complete (k−1)-partite graphs with equal nonempty parts. We first prove the case k=6 and then extend it to all k≥6 by induction.
Related
- A sharp upper bound on the number of spanning forests of regular graphs
- Sharp asymptotics for the Lovász number of random circulant graphs
- A Sharp Product Bound for Disjoint Cross-Intersecting 3-Graphs with Covering Number Three
- Yau's number-theoretic conjecture and sharp spectral bounds for quantum harmonic oscillators
- A proof of the maximum Laplacian energy conjecture for connected graphs via a sharp eigenvalue-sum bound
BibTeX
@misc{lin2026sharp,
title = {{A sharp bound on the binding number of $K_k$-free graphs and the Brandt conjecture}},
author = {Jifu Lin and Heng Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28536},
eprint = {2610.28536},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28536},
}
RIS
TY - UNPB
TI - A sharp bound on the binding number of K_k-free graphs and the Brandt conjecture
AU - Jifu Lin
AU - Heng Yang
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.28536
UR - https://arxiv.org/abs/2610.28536
AB - The binding number of a graph is the smallest ratio $|N(S)|/|S|$ among all nonempty vertex sets S whose neighborhood N(S) is not the whole vertex set. We prove that every finite nonempty K_k-free graph has binding number at most k−2 for every k≥6, confirming Brandt's conjecture; the bound is sharp for complete (k−1)-partite graphs with equal nonempty parts. We first prove the case k=6 and then extend it to all k≥6 by induction.
ER -