TxGraffiti's annihilation-number bound for connected graphs
TxGraffiti's annihilation-number bound for connected graphs
Let be a nontrivial connected graph. Write for its independence number, for its annihilation number, for its residue, and for its maximum degree.
TxGraffiti's conjecture. One has
and this bound is sharp.
The conjecture is open in general; it is established for regular bipartite and cubic Kőnig–Egerváry graphs. The bound is motivated by automated graph conjecturing and is sharp, for example, for the complete graph on four vertices.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Chakshu Gupta, “An annihilation-number Caro-Wei bound: a TxGraffiti conjecture and an independence-number bracket”, arXiv:2606.29553 (2026).
Additional references
5 papers in this index state this conjecture (2019–2026). The statement above is taken from the most recent of them; the others are arXiv:2406.19231, arXiv:2306.12917, arXiv:2104.01092, arXiv:1909.09093.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.