arXiv:2606.29553 · v2

An annihilation-number Caro-Wei bound: a TxGraffiti conjecture and an independence-number bracket

首次提交 2026-06-29 02:36

版本更新 2026-11-08 00:36

雷达观测 2026-11-10 11:14

摘要

The independence number $α$ of a finite simple graph lies between the polynomial-time computable Havel-Hakimi residue $R$ and annihilation number $a$. The Caro-Wei sum $W$ gives another lower bound and the known upper bound $α\le(Δ+1)W/2$ for maximum degree $Δ\ge1$. This upper bound does not by itself control the larger quantity $a$. This note proves $a\le(Δ+1)W/2$ for $Δ\ge1$, with equality attained, for example, by regular graphs of positive degree and even order. Together with $R\ge W$, this bound shows that the interval from $R$ to $a$ improves or matches both Caro-Wei endpoints. Its sharp worst-case endpoint ratio remains $(Δ+1)/2$, even among connected graphs. For maximum degree at least three, the bound also proves the inequality $α\ge(a+R)/Δ$ conjectured by TxGraffiti, an automated conjecturing program. A direct calculation handles connected graphs of maximum degree two. Together these cases resolve the conjecture for every connected graph with at least three vertices. The single edge is the only nontrivial connected exception. Equality holds for exactly eight connected graphs up to isomorphism. For maximum degree at least three, the conjectured lower bound never exceeds the residue, so it gives no stronger independence estimate.

作者备注：8 pages