pith. sign in

arxiv: 2606.29553 · v1 · pith:WTJSA6BEnew · submitted 2026-06-28 · 🧮 math.CO · cs.DM

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

Chakshu Gupta This is my paper

Pith reviewed 2026-06-30 02:00 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords annihilation numberCaro-Wei sumindependence numberresidueTxGraffiti conjecturedegree sequencegraph invariants
0
0 comments X

The pith

The annihilation number a satisfies a ≤ ((Δ+1)/2) W, proving the TxGraffiti conjecture on the independence number except for one graph.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the annihilation number a is at most ((Δ+1)/2) times the Caro-Wei sum W in any graph. Combined with the known facts that the independence number α is at least the residue R and at least W, this establishes the inequality α ≥ (a + R)/Δ for every connected graph with maximum degree at least two. The same relation places α between the polynomial-time quantities R and a, up to the factor (Δ+1)/2. A reader would care because these bounds give concrete, efficiently computable estimates for a quantity that is otherwise hard to determine exactly.

Core claim

The note proves the degree-sequence inequality a ≤ ((Δ+1)/2) W. Combined with the classical lower bounds α ≥ R and α ≥ W, it proves the conjecture α ≥ (a + R)/Δ for every connected graph of maximum degree at least three, and a direct argument settles maximum degree two; the conjecture fails only for the single edge, of maximum degree one. The inequality also brackets the independence number between the polynomial-time quantities R and a, within a factor (Δ+1)/2. The conjecture's bound is sharp, with equality attained, for instance, by the complete graph on four vertices.

What carries the argument

The degree-sequence inequality a ≤ ((Δ+1)/2) W relating the annihilation number to the Caro-Wei sum, which is then combined with the residue to bound the independence number.

If this is right

  • The TxGraffiti conjecture holds for every connected graph with maximum degree at least two.
  • The independence number is bracketed between the residue R and the annihilation number a within a factor of (Δ+1)/2.
  • The bound a ≤ ((Δ+1)/2) W is attained by the complete graph K4.
  • All three quantities R, a, and W remain polynomial-time computable while supplying the stated bounds on α.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The bracketing supplies a concrete way to approximate the independence number using only polynomial-time invariants for any fixed maximum degree.
  • The same style of degree-sequence comparison may resolve other open inequalities between graph invariants generated by automated conjecturing programs.
  • It would be natural to test whether the factor (Δ+1)/2 can be replaced by a smaller constant on restricted graph families such as planar or bipartite graphs.

Load-bearing premise

The classical lower bounds α ≥ R and α ≥ W hold for all graphs.

What would settle it

Any graph in which the annihilation number exceeds ((Δ+1)/2) times the Caro-Wei sum would falsify the central inequality.

read the original abstract

Automated conjecturing programs scan collections of graphs for inequalities between invariants that no stored graph violates, then offer the survivors for proof or refutation. TxGraffiti, one such program, conjectured that every nontrivial connected graph $G$ satisfies $\alpha(G) \ge \bigl(a(G) + R(G)\bigr)/\Delta(G)$, where $\alpha$ is the independence number, $a$ the annihilation number, $R$ the residue, and $\Delta$ the maximum degree. Established only for two special families of graphs, the conjecture has otherwise remained open. The note proves the degree-sequence inequality $a \le \tfrac{\Delta+1}{2}W$, where $W$ is the Caro-Wei sum; the same inequality is known for the independence number in place of $a$. Combined with the classical lower bounds $\alpha \ge R$ and $\alpha \ge W$, it proves the conjecture for every connected graph of maximum degree at least three, and a direct argument settles maximum degree two; the conjecture fails only for the single edge, of maximum degree one. The inequality also brackets the independence number between the polynomial-time quantities $R$ and $a$, within a factor $(\Delta+1)/2$. The conjecture's bound is sharp, with equality attained, for instance, by the complete graph on four vertices.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper proves the TxGraffiti conjecture that every nontrivial connected graph G satisfies α(G) ≥ (a(G) + R(G))/Δ(G), where α is the independence number, a the annihilation number, R the residue, and Δ the maximum degree. The proof establishes the new degree-sequence inequality a(G) ≤ ((Δ+1)/2) W(G) (with W the Caro-Wei sum) and combines it with the classical bounds α ≥ R and α ≥ W; this settles the conjecture for all connected graphs with Δ ≥ 2 (with a direct argument for Δ = 2) and shows failure only for K2. The same inequality is used to bracket α between the polynomial-time computable quantities R and a within a multiplicative factor of (Δ+1)/2. Equality is attained, e.g., by K4.

Significance. If the central inequality holds, the manuscript supplies a clean, parameter-free proof of an automated conjecture, introduces a new Caro-Wei-type bound for the annihilation number that parallels the known bound for α, and yields an explicit polynomial-time sandwich for the independence number. The argument relies only on standard external facts (α ≥ R, α ≥ W) plus one algebraic comparison whose coefficient simplifies to (Δ+3)/(2Δ) ≤ 1 for Δ ≥ 3; this is a genuine strength for a short note in combinatorial graph theory.

minor comments (1)
  1. The abstract and introduction should explicitly recall the definitions of a(G), R(G), and W(G) (or give precise references) so that readers need not consult external sources for the basic notation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive evaluation of the manuscript and the recommendation to accept. The report accurately summarizes the main results, including the proof of the TxGraffiti conjecture via the new bound a(G) ≤ ((Δ+1)/2)W(G) and the resulting sandwich for α(G).

Circularity Check

0 steps flagged

No significant circularity; derivation uses external classical bounds

full rationale

The paper establishes a new inequality a(G) ≤ ((Δ+1)/2) W(G) for the annihilation number and combines it with the independently known classical facts α(G) ≥ R(G) and α(G) ≥ W(G). These classical bounds predate the paper and hold for all graphs; the algebraic combination that yields the TxGraffiti conjecture for Δ ≥ 3 introduces no self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on classical bounds and the new proved inequality; no free parameters or invented entities.

axioms (2)
  • domain assumption The classical inequalities α ≥ R and α ≥ W hold for all graphs.
    Invoked to combine with the new bound on a to prove the conjecture.
  • standard math Standard properties of graph degree sequences and the definitions of a, R, W, α, Δ.
    Background assumptions in combinatorial graph theory.

pith-pipeline@v0.9.1-grok · 5772 in / 1512 out tokens · 63245 ms · 2026-06-30T02:00:28.518098+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references

  1. [1]

    Boppana, Magn \'u s M

    Ravi B. Boppana, Magn \'u s M. Halld \'o rsson, and Dror Rawitz. Simple and local independent set approximation. In Structural Information and Communication Complexity (SIROCCO 2018) , volume 11085 of Lecture Notes in Comput. Sci. , pages 88--101. Springer, 2018

    2018

  2. [2]

    New results on the independence number

    Yair Caro. New results on the independence number. Technical report, Tel-Aviv University, 1979

    1979

  3. [3]

    Degree sequence index strategy

    Yair Caro and Ryan Pepper. Degree sequence index strategy. Australas. J. Combin. , 59(1):1--23, 2014

    2014

  4. [4]

    In reverie together: Ten years of mathematical discovery with a machine collaborator, 2025

    Randy Davila, Boris Brimkov, and Ryan Pepper. In reverie together: Ten years of mathematical discovery with a machine collaborator, 2025. Preprint, July 2025

    2025

  5. [5]

    On conjectures of Graffiti

    Siemion Fajtlowicz. On conjectures of Graffiti . Discrete Math. , 72(1-3):113--118, 1988

    1988

  6. [6]

    On the residue of a graph

    Odile Favaron, Maryvonne Mah \'e o, and Jean-Fran c ois Sacl \'e . On the residue of a graph. J. Graph Theory , 15(1):39--64, 1991

    1991

  7. [7]

    S. L. Hakimi. On realizability of a set of integers as degrees of the vertices of a linear graph. I . J. Soc. Indust. Appl. Math. , 10(3):496--506, 1962

    1962

  8. [8]

    Pozn \'a mka o existenci kone c n \'y ch graf u

    V \'a clav Havel. Pozn \'a mka o existenci kone c n \'y ch graf u . C asopis pro p e stov \'a n \' matematiky , 80:477--480, 1955

    1955

  9. [9]

    Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Complexity of Computer Computations , pages 85--103. Plenum Press, New York, 1972. Reprinted in: 50 Years of Integer Programming 1958--2008 (M. J \"u nger et al., eds.), Springer, 2010, pp. 219--241

    1972

  10. [10]

    McKay and Adolfo Piperno

    Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II . J. Symbolic Comput. , 60:94--112, 2014

    2014

  11. [11]

    On the annihilation number of a graph

    Ryan Pepper. On the annihilation number of a graph. In Proceedings of the 15th American Conference on Applied Mathematics (AMERICAN-MATH'09) , pages 217--220. WSEAS Press, 2009

    2009

  12. [12]

    Victor K. Wei. A lower bound on the stability number of a simple graph. Technical Memorandum 81-11217-9, Bell Laboratories, Murray Hill, NJ, 1981

    1981