no. 15 · Monday 16 November 2026
An annihilation-number Caro-Wei bound: a TxGraffiti conjecture and an independence-number bracket
Abstract
Computable independence bounds give intervals that can be compared by containment or by their worst-case endpoint ratios. For positive maximum degree $Δ$, the Caro-Wei sum $W$ bounds the independence number from below, while $(Δ+1)W/2$ bounds it from above. A second interval has the Havel-Hakimi residue as its lower endpoint and the annihilation number as its upper endpoint. This note proves that the annihilation number does not exceed the Caro-Wei upper endpoint. This upper bound is sharp, with equality for regular graphs of positive degree and even order. Since the residue is at least $W$, this upper bound places the residue-annihilation interval inside the Caro-Wei interval. Both endpoints can improve strictly on one graph, although the sharp worst-case endpoint ratio remains unchanged, even for connected graphs. The annihilation-number bound also proves a conjectured lower estimate based on the annihilation number and residue for every connected graph with at least three vertices. Equality in this estimate holds for exactly eight graph types, while the single edge violates it. For maximum degree at least three, however, the estimate never exceeds the residue, even without connectedness.
- comments
- 9 pages
- fields
- Combinatorics