A counterexample to a conjecture of Jia and Song on remoteness and the second largest distance eigenvalue

Résumé fourni par la source

We disprove a conjecture of Jia and Song (J. Inequal. Appl. 2018:69, Conjecture 3.8), later reproduced as Conjecture 1 in the survey of Aouchiche and Rather (Discrete Appl. Math. 353 (2024) 94–120), concerning the sum of the remoteness ρ and the second largest distance eigenvalue ∂₂ of a connected graph. The conjecture asserts that every connected graph G ≇ Kₙ, Kₙ−e of order n ≥ 4 satisfies ρ + ∂₂ ≥ n/(n−1) + ((n−1)−√((n−1)²+8))/2, with equality if and only if G ≅ Kₙ−2e. We show this is false. The bowtie (two triangles sharing a vertex, n = 5) is a counterexample, certified by the elementary rational inequality 3456 < 3481. More generally, writing H(a,b) = K₁ ∨ (Kₐ ∪ K_b), the graphs H(m,m) violate the inequality for every odd order n = 2m+1 ≥ 5 and H(m+1,m) for every even order n = 2m+2 ≥ 10; the deficit tends to 1/6. We further prove that the claimed extremal graph Kₙ−2e attains equality for no n, in fact ∂₂(Kₙ−2e) = 0, so the conjectured right-hand side is exactly ρ + ∂₂ of Kₙ−e, a graph excluded by the hypothesis. We reconstruct the origin of the error and explain why the proof method used for the analogous ∂₁ bounds does not transpose to ∂₂, the obstruction being that ∂₂ is not monotone under edge deletion. Finally we propose a corrected conjecture, with extremal graph H(⌈(n−1)/2⌉, ⌊(n−1)/2⌋), verified computationally for n ≤ 11 (exhaustively for n ≤ 10; at n = 11 over a provably complete subclass). All spectra and inequalities are exact; the computations serve only as verification, not as ingredients of the proofs.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.