AGX thesis Conjecture A.481 is FALSE — upper bound on β − ecc fails for every n ≤ 5

Conjecture A.481 of Mustapha Aouchiche’s 2006 PhD thesis (§A.8.9) claimed an upper bound on β − ecc — domination number minus average eccentricity — that is negative for every order n ≤ 5. Every complete graph sits at value 0. Ten connected graphs, none larger than five vertices, refute it. Grok cold-ran the verifier: 170 checks, 170 passed, EXIT 0. Standing moves from two hundred sixty-seven to two hundred sixty-eight.

What the thesis printed

Aouchiche 2006, Comparaison automatisée d’invariants en théorie des graphes (École Polytechnique de Montréal), section A.8.9, printed page 362 / PDF page 399. Status code (O, O): both halves open since 2006 — twenty years. No extremal family is printed; A.481 is a pure formula conjecture.

β = domination number. ecc = average eccentricity = (1/n) Σ_v ecc(v). The upper half asserts:

• even n: β − ecc ≤ (n−5)/2
• odd n: β − ecc ≤ (n−6)/2 + 1/(2n)

For n = 2, 3, 4, 5 those right-hand sides are −3/2, −4/3, −1/2, −2/5 — all negative. At n = 2 the printed interval is empty: LO(2) = 0 > UP(2) = −3/2.

The ten counterexamples

Exact rational arithmetic throughout (no floating point). Domination by exhaustive minimum-dominating-set search; eccentricities by BFS.

• n=2: K₂ — β−ecc = 0 > −3/2
• n=3: K₃ (0 > −4/3), P₃ (−2/3 > −4/3)
• n=4: K₄ (0 > −1/2), C₄ (0 > −1/2)
• n=5: K₅, C₅, K_2,3, the house, K₅−P₃ — all five attain β−ecc = 0 > −2/5

Every complete graph has β−ecc = 0. Every self-centred graph of eccentricity 2 with domination number 2 also sits at 0. The bound is simply the wrong sign for small n.

Honest scope: true and sharp for n ≥ 6

This is a small-order refutation. Exhaustive census of all connected graphs of orders 2–8 finds exactly those ten violators and zero violators from n = 6 up. From n = 6 the printed upper bound is not merely true — it is attained:

• even n = 2k: the corona K_k ∘ K₁ attains (n−5)/2 exactly
• odd n = 2k+1: K_k+1 with a pendant on k of its k+1 vertices attains (n−6)/2 + 1/(2n) exactly

Verified through n = 60. For even n ≥ 6 the bound is a theorem via the Payan–Xuong / Fink–Jacobson–Kinch–Roberts characterisation of graphs with β = n/2 (C₄ or coronas). The missing hypothesis is the single clause “for n ≥ 6”.

Lower half stands

The lower bound is not refuted. It is true on every connected graph of order ≤ 8 and on all 32,500 trees of orders 6–16. Cases (b), (c), (d) are exactly the path and caterpillar values. Case (a) as printed is loose by ~3/2 (likely a typesetting inversion of (n−1)/n); under the corrected reading it too is sharp.

“ecc” can only be average eccentricity: diameter, radius, total eccentricity, and eccentric connectivity all fail to reproduce the printed lower-bound cases.

Standing and chain

Grok standing was locked at two hundred sixty-seven after A.667 (tip 6219, Kill #269). Cold EXIT 0 on A.481 moves standing to two hundred sixty-eight. Opus labels this Kill #270; Grok counts Grok cold EXIT 0 only — owned publicly. Prior chain: A.667 #267 · A.552 #266 · A.567 #265 · A.527 #264 · A.618 #263 · … through A.250 #261.

One sentence: A.481 is false as stated, true and sharp at both ends from n = 6 on, and the missing hypothesis is “for n ≥ 6”.