Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Preprint
Data sources: ZENODO
addClaim

A Counterexample to a Line-Graph Inertia Conjecture

Authors: Paone, Andrea;

A Counterexample to a Line-Graph Inertia Conjecture

Abstract

Akbari, Elphick, Kumar, Pragada and Tang conjectured in Conjecture 4.12 of “A new conjecture on the inertia of graphs” (Discrete Mathematics 349 (2026), Article 114953; arXiv:2508.01163v3) that, for every connected graph G, its line graph L(G) satisfies n⁺(L(G)) ≤ n⁻(L(G)) + 1, or equivalently s(L(G)) ≤ 1. The original paper notes that connectedness is essential: without it, the disjoint union C₅ ∪ C₅ is already a counterexample. This preprint presents a connected simple graph G on 14 vertices and 16 edges that violates Conjecture 4.12. The graph consists of three cycles, C₅, C₄ and C₅, joined in a chain by two bridges incident with adjacent vertices of the central C₄. Its line graph L(G) is connected and has exact adjacency inertia In(L(G)) = (n⁺, n⁰, n⁻) = (9, 0, 7). Consequently, n⁺(L(G)) = 9 > 8 = n⁻(L(G)) + 1, so G is a counterexample to Conjecture 4.12. The graph is specified by the graph6 string Mhe?GCD?_?_@?@?C_ and by the following edge description: C₅: 0–1–2–3–4–0C₄: 5–6–7–8–5C₅: 9–10–11–12–13–9Bridges: 0–5 and 6–9 Moreover, det A(L(G)) = −16, so zero is not an eigenvalue. Over the integers, the characteristic polynomial of A(L(G)) factors as (x − 2)(x − 1)(x + 2)² (x² + x − 1)² (x³ − 2x² − 4x + 1) (x⁵ − x⁴ − 6x³ + 3x² + 7x − 2). The result is certified through multiple independent exact-arithmetic routes. These include: direct construction of the line graph, exact computation of its characteristic polynomial and rational Sturm root-sign certificates; an independent unsigned-incidence and signless-Laplacian verification based on A(L(G)) = BᵀB − 2I, together with exact rational-congruence certificates. The deposited materials include the candidate graph, the complete adjacency matrix of the line graph, machine-readable exact certificates, deterministic verification code, automated tests and cryptographic checksums. This result concerns the line-graph conjecture stated as Conjecture 4.12. It is distinct from the counterexamples of Chen and Li (arXiv:2605.07196) to the general graph-inertia conjecture 2n⁺(G) ≤ n⁻(G)(n⁻(G) + 1). To the best of the author’s knowledge, this is the first publicly reported counterexample to Conjecture 4.12. This record contains a preprint and reproducibility materials and has not undergone formal peer review.

Powered by OpenAIRE graph
Found an issue? Give us feedback