Unbounded Signature of Line Graphs:
Counterexamples and Transfer Principles

Andrea Paone
Independent researcher, Italy
ORCID: 0009-0003-6194-948X

(Version 2.0 — 24 July 2026
Bibliographic revision 1 — 29 July 2026)

Abstract

Akbari, Elphick, Kumar, Pragada, and Tang conjectured that every connected graph $G$ satisfies

n_{+}(L(G))\leq n_{-}(L(G))+1,

where $L(G)$ denotes the line graph and $n_{+},n_{-}$ are the positive and negative adjacency inertia indices. A previous Version 1 manuscript, publicly archived on Zenodo, identified a connected simple graph $G_{0}$ with $\operatorname{In}(L(G_{0}))=(9,0,7)$ . No priority or first-counterexample claim is made here.

We show that the failure is unbounded even under strong structural restrictions. We prove a rooted-module attachment lemma: if a rooted graph module $M$ has invertible line-graph adjacency matrix $K$ and the diagonal entry of $K^{-1}$ corresponding to the root edge is zero, then attaching $M$ to any host vertex gives a line-graph adjacency matrix congruent to $A(L(H))\oplus K$ . A specific rooted $C_{4}$ – $C_{5}$ module has $\operatorname{In}(K)=(6,0,5)$ and determinant $-8$ . Iterating it produces connected simple planar subcubic cactus graphs $F_{k}$ satisfying

\operatorname{In}(L(F_{k}))=(6k+3,0,5k+2),\qquad\det A(L(F_{k}))=2(-8)^{k}.

Hence $\operatorname{sig}(L(F_{k}))=k+1$ and the conjectured inequality fails by $k$ .

Earlier internal-path work of Ma, Yang, and Li, as used by Wang and Fan for line-graph signatures, already gives the real-inertia period-four phenomenon. Here we prove the more specific arbitrary-edge line-graph statement that four subdivisions admit an explicit integral unimodular congruence. It changes inertia by $(2,0,2)$ and preserves determinant, adjacency cokernel, nonunit Smith invariant factors, and nullity over every field. This gives a modulo-four reduction for arbitrary subdivision vectors. As an application, a computer-assisted exact classification of all three-cycle chains shows that counterexamples occur precisely when both terminal cycles have length $1$ modulo $4$ and the two central attachment arcs have residues $1$ and $3$ modulo $4$ .

Keywords: graph inertia; line graph; graph signature; cactus graph; edge subdivision; congruence; Smith normal form; counterexample.

MSC 2020: 05C50; 15A18.

Revision note, 29 July 2026. This bibliographic revision adds a citation to the independent contemporaneous work of Francis and Uptain and clarifies the relationship between the two unboundedness constructions. No theorem, proof, exact certificate, computational output, or numerical statement from Version 2.0 has been changed.

1 Introduction

For a graph $X$ with adjacency matrix $A(X)$ , write

\operatorname{In}(X)=\bigl{(}n_{+}(X),n_{0}(X),n_{-}(X)\bigr{)}

and

\operatorname{sig}(X)=n_{+}(X)-n_{-}(X).

Akbari et al. [1] proposed, as Conjecture 4.12, that every connected graph $G$ satisfies

n_{+}(L(G))\leq n_{-}(L(G))+1,

(1)

that is, $\operatorname{sig}(L(G))\leq 1$ .

The original paper reported no counterexample among numerous tested graphs with $|E(G)|=|V(L(G))|\leq 100$ , and no counterexample among graphs of order at most nine. It proved the conjecture for line graphs of trees and for the dense range $m\geq 2n-1$ , leaving the range $n\leq m\leq 2n-2$ open. The graph $G_{0}$ from the Version 1 manuscript [10] has $n=14$ and $m=16$ , so it lies in that open range and above the exhaustive order-nine search. Its line graph has inertia $(9,0,7)$ and signature two.

The present work addresses two questions left by a single finite counterexample.

(i)

Is the failure isolated, or does it persist in an infinite structural family?
(ii)

Is the amount by which (1) fails bounded?

The second question has a stronger answer: the failure is unbounded even when $G$ is required to be connected, simple, planar, subcubic, and a cactus graph. The mechanism is a local rooted module that increases the line-graph signature by exactly one whenever it is attached.

Independently and contemporaneously, Francis and Uptain [5] obtained a counterexample isomorphic to the 14-vertex graph of Version 1 and proved that the signature of connected line graphs is unbounded by chaining copies of that entire seed. Their construction uses bridges between seed copies and a signless-Laplacian resolvent argument. By contrast, the construction developed here iterates a rooted $C_{4}$ – $C_{5}$ module on arbitrary hosts and yields the alternating cycle family $C_{5},(C_{4},C_{5})^{k}$ ; the two arguments establish the same global phenomenon through distinct structural mechanisms. Among the public records currently identified, Version 1, deposited on 22 July 2026, is the earliest public record of the finite counterexample. The present Version 2 and the Francis–Uptain public records are both dated 24 July 2026, and no claim of intra-day priority for unboundedness is made here.

Ma, Yang, and Li established a real-inertia reduction along internal paths, and Wang and Fan used that period-four mechanism in line-graph signature work [9, 11]. The contribution here is narrower and stronger at the arithmetic level: for four subdivisions of an arbitrary root edge, we give an explicit integral unimodular congruence for the line-graph adjacency matrix. This yields the determinant, cokernel, nonunit Smith-factor, and field-nullity consequences used below, and permits a finite exact classification of the three-cycle-chain class containing $G_{0}$ .

The main contributions are:

(1)

a general rooted-module attachment formula for line-graph adjacency inertia;
(2)

an exact amplifier module with inertia increment $(6,0,5)$ ;
(3)

an alternating cycle-chain family with signature $k+1$ ;
(4)

an explicit arbitrary-edge integral unimodular four-subdivision congruence, refining the previously known real-inertia period-four reduction;
(5)

arithmetic corollaries for Smith normal form and adjacency cokernels;
(6)

an exact modulo-four classification of all three-cycle chains.

Closest related work also includes Ma and Xie’s inertia analysis of a special tricyclic class [8], Jog and Kotambari’s spectral study of special complete-graph coalescences [7], and Fan, Zhang, and Wang’s polynomial Smith-form results for coalescence at cospectral vertices [3], and He and Shan’s signature analysis of two generalizations of line graphs [6]. These works are methodologically adjacent but do not give the present line-graph residue classification, arbitrary-host zero-response attachment formula, or arbitrary-edge integral transfer.

Chen and Li [2] refute a different conjecture from [1], namely a global quadratic inequality for arbitrary graphs. Their result does not address Conjecture 4.12.

2 Preliminaries

All graphs are finite and simple. For a graph $G$ , its line graph $L(G)$ has vertex set $E(G)$ , with two vertices adjacent exactly when the corresponding root-graph edges share an endpoint.

Two real symmetric matrices $P$ and $Q$ are congruent if $Q=T^{\mathsf{T}}PT$ for some nonsingular matrix $T$ . By Sylvester’s law of inertia, congruent real symmetric matrices have the same inertia. If $T$ is an integer matrix with determinant $\pm 1$ , the congruence is integral and unimodular.

We use the hyperbolic block

J=\begin{pmatrix}0&1\\ 1&0\end{pmatrix},\qquad\operatorname{In}(J)=(1,0,1),\qquad\det J=-1.

The following standard block identity will be used repeatedly.

Lemma 2.1 (Symmetric Schur elimination).

Let

Q=\begin{pmatrix}A&C\\ C^{\mathsf{T}}&K\end{pmatrix}

be symmetric, with $K$ invertible. Then

Q\sim\bigl{(}A-CK^{-1}C^{\mathsf{T}}\bigr{)}\oplus K.

More explicitly,

\begin{pmatrix}I&0\\ -K^{-1}C^{\mathsf{T}}&I\end{pmatrix}^{\!\mathsf{T}}Q\begin{pmatrix}I&0\\ -K^{-1}C^{\mathsf{T}}&I\end{pmatrix}=\bigl{(}A-CK^{-1}C^{\mathsf{T}}\bigr{)}% \oplus K.

3 The seed counterexample

Let $G_{0}$ have vertex set $\{0,1,\ldots,13\}$ and edge set

	$\displaystyle E(G_{0})=\{$	$\displaystyle(0,1),(1,2),(2,3),(3,4),(4,0),$
		$\displaystyle(5,6),(6,7),(7,8),(8,5),$
		$\displaystyle(9,10),(10,11),(11,12),(12,13),(13,9),$
		$\displaystyle(0,5),(6,9)\}.$

Thus $G_{0}$ is a chain $C_{5}$ – $C_{4}$ – $C_{5}$ , with the bridges meeting adjacent vertices of the central $C_{4}$ .

The exact characteristic polynomial of $A(L(G_{0}))$ factors as

$\displaystyle\chi_{0}(x)={}$	$\displaystyle(x-2)(x-1)(x+2)^{2}(x^{2}+x-1)^{2}$
	$\displaystyle\cdot(x^{3}-2x^{2}-4x+1)$
	$\displaystyle\cdot(x^{5}-x^{4}-6x^{3}+3x^{2}+7x-2).$	(2)

Exact rational root isolation gives

\operatorname{In}(L(G_{0}))=(9,0,7),\qquad\det A(L(G_{0}))=-16.

(3)

An involution exchanges the two terminal $C_{5}$ cycles and reflects the central $C_{4}$ . In symmetry-adapted bases, the two invariant blocks have inertias $(5,0,4)$ and $(4,0,3)$ . Hence each sector contributes one unit of signature. This observation motivates a modular rather than accidental interpretation of the seed.

4 Rooted-module attachment

Definition 4.1.

Let $M$ be a graph with a distinguished root vertex $r$ of degree one, and let $\rho=rs$ be its unique incident edge. If $H$ is vertex-disjoint from $M$ and $v\in V(H)$ , write $H\star_{v}M$ for the graph obtained by identifying $r$ with $v$ .

Theorem 4.2 (Rooted-module attachment).

Let

A=A(L(H)),\qquad K=A(L(M)).

Assume $K$ is invertible. Let $e_{\rho}$ denote the coordinate vector of the root edge in $L(M)$ , and let $z$ be the indicator vector of the edges of $H$ incident with $v$ . Then

A(L(H\star_{v}M))\sim\left(A-\alpha zz^{\mathsf{T}}\right)\oplus K,\qquad% \alpha=(K^{-1})_{\rho\rho}.

(4)

In particular, if $(K^{-1})_{\rho\rho}=0$ , then

A(L(H\star_{v}M))\sim A(L(H))\oplus K.

(5)

Proof.

Order the vertices of the new line graph first by $E(H)$ and then by $E(M)$ . The only new edge of $M$ adjacent in the line graph to old edges of $H$ is the root edge $\rho$ . It is adjacent precisely to the old edges incident with $v$ . Therefore

A(L(H\star_{v}M))=\begin{pmatrix}A&ze_{\rho}^{\mathsf{T}}\\ e_{\rho}z^{\mathsf{T}}&K\end{pmatrix}.

Applying Lemma 2.1 gives the Schur complement

A-ze_{\rho}^{\mathsf{T}}K^{-1}e_{\rho}z^{\mathsf{T}}=A-(K^{-1})_{\rho\rho}zz^{% \mathsf{T}},

which proves (4). The zero-diagonal case gives (5). ∎

Corollary 4.3.

Under the zero-diagonal hypothesis,

\operatorname{In}(L(H\star_{v}M))=\operatorname{In}(L(H))+\operatorname{In}(K)

and

\det A(L(H\star_{v}M))=\det A(L(H))\det K.

5 A signature amplifier

Let $M$ be the rooted graph with vertices

r,x_{0},x_{1},x_{2},x_{3},y_{0},y_{1},y_{2},y_{3},y_{4}

and edges

	$\displaystyle\rho$	$\displaystyle=rx_{0},$
		$\displaystyle x_{0}x_{1},x_{1}x_{2},x_{2}x_{3},x_{3}x_{0},$
		$\displaystyle x_{1}y_{0},$
		$\displaystyle y_{0}y_{1},y_{1}y_{2},y_{2}y_{3},y_{3}y_{4},y_{4}y_{0}.$

Thus a pendant root edge is followed by a $C_{4}$ and a $C_{5}$ , with the two connections meeting adjacent vertices of the $C_{4}$ .

Order the edges as listed and let $K=A(L(M))$ .

Proposition 5.1 (Amplifier certificate).

The matrix $K$ satisfies

\operatorname{In}(K)=(6,0,5),\qquad\det K=-8,\qquad(K^{-1})_{\rho\rho}=0.

Proof.

Exact symmetric elimination over $\mathbb{Q}$ gives the congruence certificate

K\sim J\oplus[-2]\oplus[1/2]\oplus 2J\oplus J\oplus J\oplus[2].

(6)

The four hyperbolic blocks contribute $(4,0,4)$ , the positive scalar blocks contribute two positive directions, and the scalar $-2$ contributes one negative direction. Hence $\operatorname{In}(K)=(6,0,5)$ . The product of the displayed block determinants is $-8$ , so $K$ is invertible.

For the inverse diagonal, set

w=(0,1/2,-1/2,-1/2,1/2,0,0,0,0,0,0)^{\mathsf{T}}.

Direct multiplication in the stated edge order gives

Kw=e_{\rho}.

Thus $w=K^{-1}e_{\rho}$ . Its root coordinate is zero, proving $(K^{-1})_{\rho\rho}=0$ . ∎

Corollary 5.2 (One-step amplification).

For every finite simple host graph $H$ and every vertex $v\in V(H)$ ,

\operatorname{In}(L(H\star_{v}M))=\operatorname{In}(L(H))+(6,0,5)

and

\det A(L(H\star_{v}M))=-8\det A(L(H)).

In particular, every attachment increases line-graph signature by one.

6 Unbounded signature on a restricted graph class

Definition 6.1.

Let $F_{0}=C_{5}$ , with one selected vertex. Define $F_{1}$ by attaching one copy of the module $M$ at that selected vertex. For $k\geq 2$ , obtain $F_{k}$ from $F_{k-1}$ by attaching one copy of $M$ to a vertex adjacent to the incoming bridge vertex on the terminal $C_{5}$ . The two such vertices are interchanged by the reflection of that $C_{5}$ fixing the incoming bridge vertex, so both choices give isomorphic graphs and $F_{k}$ is well defined up to isomorphism. Equivalently, $F_{k}$ is the cactus chain with cycle sequence

C_{5},C_{4},C_{5},C_{4},\ldots,C_{4},C_{5},

containing $k+1$ copies of $C_{5}$ and $k$ copies of $C_{4}$ , with adjacent bridge attachments in every internal cycle.

Theorem 6.2 (Unbounded signature).

For every integer $k\geq 0$ ,

$\displaystyle\|V(F_{k})\|$	$\displaystyle=9k+5,$	(7)
$\displaystyle\|E(F_{k})\|$	$\displaystyle=11k+5,$	(8)
$\displaystyle\operatorname{In}(L(F_{k}))$	$\displaystyle=(6k+3,0,5k+2),$	(9)
$\displaystyle\det A(L(F_{k}))$	$\displaystyle=2(-8)^{k}.$	(10)

Consequently,

\operatorname{sig}(L(F_{k}))=k+1

(11)

and

n_{+}(L(F_{k}))-\bigl{(}n_{-}(L(F_{k}))+1\bigr{)}=k.

(12)

Proof.

Since $L(C_{5})\cong C_{5}$ ,

\operatorname{In}(L(F_{0}))=(3,0,2),\qquad\det A(L(F_{0}))=2.

The explicitly defined step $F_{0}\mapsto F_{1}$ and every subsequent step $F_{k-1}\mapsto F_{k}$ are rooted-module attachments. By Corollary 5.2, each adds $(6,0,5)$ to inertia and multiplies the determinant by $-8$ . Induction proves the spectral formulas.

After identification of the root, each module contributes nine new vertices and eleven new edges. This proves the order and size formulas. The signature and violation formulas follow by subtraction. ∎

Corollary 6.3.

The signature of line graphs is unbounded above even when the root graphs are restricted to connected simple planar subcubic cactus graphs.

Proof.

Every $F_{k}$ has the stated graph-theoretic properties, and $\operatorname{sig}(L(F_{k}))=k+1$ tends to infinity. ∎

The seed counterexample is $F_{1}$ . Thus its one-unit violation is the initial nontrivial term of a family whose violation grows without bound.

7 Four-subdivision transfer and prior period-four reduction

The real-inertia increment under removal or insertion of a suitable four-vertex internal-path segment predates this work [9]; Wang and Fan used this mechanism in their analysis of line-graph signatures [11]. The theorem below does not claim priority for the $(2,0,2)$ inertia change. Its distinct contribution is an explicit congruence over $\mathbb{Z}$ for four subdivisions of an arbitrary root edge, with a unimodular transformation and the arithmetic consequences that follow from it.

The amplifier changes signature. A second local operation preserves it and explains the modulo-four structure of the cycle lengths.

Definition 7.1.

For an edge $e=uv$ of a graph $G$ , let $S_{4}(G,e)$ be obtained by deleting $u v$ , adding four new vertices $w_{1},w_{2},w_{3},w_{4}$ , and inserting the path

u-w_{1}-w_{2}-w_{3}-w_{4}-v.

Let its five consecutive edges be $e_{1},e_{2},e_{3},e_{4},e_{5}$ .

Theorem 7.2 (Four-subdivision transfer).

For every finite simple graph $G$ and edge $e$ ,

A(L(S_{4}(G,e)))\cong_{\mathbb{Z}}A(L(G))\oplus J\oplus J,

(13)

where $\cong_{\mathbb{Z}}$ denotes integral unimodular congruence. Hence

\operatorname{In}(L(S_{4}(G,e)))=\operatorname{In}(L(G))+(2,0,2).

(14)

Proof.

Let $R=E(G)\setminus\{e\}$ and order $L(G)$ by $R, e$ :

A(L(G))=\begin{pmatrix}M&z\\ z^{\mathsf{T}}&0\end{pmatrix}.

Order $L(S_{4}(G,e))$ as

R,e_{3}\mid e_{1},e_{2},e_{4},e_{5}.

Write the resulting matrix as

\begin{pmatrix}B&C\\ C^{\mathsf{T}}&K_{0}\end{pmatrix}.

The final four edge-vertices induce two disjoint edges, so $K_{0}=J\oplus J$ and $K_{0}^{-1}=K_{0}$ .

If $z=a+b$ , where $a$ and $b$ record old edges incident with $u$ and $v$ , then

B=\begin{pmatrix}M&0\\ 0&0\end{pmatrix},\qquad C=\begin{pmatrix}a&0&0&b\\ 0&1&1&0\end{pmatrix}.

A direct multiplication gives

B-CK_{0}C^{\mathsf{T}}=\begin{pmatrix}M&-z\\ -z^{\mathsf{T}}&0\end{pmatrix}=DA(L(G))D,

where $D=\operatorname{diag}(I,-1)$ .

Lemma 2.1, followed by the sign switch $D$ , gives (13). Every matrix used has integer entries and determinant $\pm 1$ , so the congruence is integral and unimodular. Equation (14) follows from $\operatorname{In}(J\oplus J)=(2,0,2)$ . ∎

Corollary 7.3.

Four-subdivision preserves:

(i)

line-graph signature and nullity;
(ii)

determinant and nonsingularity;
(iii)

the conjecture-violation margin $n_{+}(L(G))-n_{-}(L(G))-1$ ;
(iv)

the adjacency cokernel;
(v)

all nonunit Smith invariant factors;
(vi)

adjacency nullity over every field.

Proof.

The first three claims follow from (13). The block $J\oplus J$ is unimodular and has Smith normal form $I_{4}$ , so it contributes four unit invariant factors and trivial cokernel. Reducing the same unimodular congruence over an arbitrary field shows that rank increases by four and nullity is unchanged. ∎

Corollary 7.4 (Modulo-four reduction).

If an edge is subdivided $r=4q+\rho$ times, where $0\leq\rho\leq 3$ , then

\operatorname{In}(L(G_{e}^{(r)}))=\operatorname{In}(L(G_{e}^{(\rho)}))+(2q,0,2% q).

More generally, for a fixed homeomorphism core, the line-graph signature and nullity of all subdivisions depend only on the subdivision vector modulo four.

8 Fixed-signature families

The four-subdivision theorem gives families in which the signature remains two. For nonnegative $a, b, c, d$ , let $G(a,b,c,d)$ be the three-cycle chain with terminal cycle lengths $4a+5$ and $4b+5$ , and central attachment-arc lengths $4c+1$ and $4d+3$ .

Theorem 8.1.

Let $q=a+b+c+d$ . Then

\operatorname{In}(L(G(a,b,c,d)))=(9+2q,0,7+2q)

and

\det A(L(G(a,b,c,d)))=-16.

Every member is a connected planar subcubic cactus counterexample of signature two.

Proof.

The graph is obtained from $G_{0}$ by $q$ four-subdivisions, distributed among the two terminal cycles and the two central arcs. Apply Theorem 7.2 repeatedly. ∎

9 Exact classification of three-cycle chains

Definition 9.1.

Let $T(p,q;s,t)$ be the graph formed from terminal cycles $C_{p}$ and $C_{q}$ and a central cycle whose two bridge-attachment vertices divide it into arcs of lengths $s$ and $t$ . Assume

p,q\geq 3,\qquad s,t\geq 1,\qquad s+t\geq 3.

Theorem 9.2 (Computer-assisted exact classification).

The graph $T(p,q;s,t)$ violates (1) if and only if

p\equiv q\equiv 1\pmod{4}

and

\{s\bmod 4,t\bmod 4\}=\{1,3\}.

Every such graph has line-graph signature exactly two. All other graphs in this class have line-graph signature at most one.

Exact finite certificate.

By Corollary 7.4, it is enough to examine the $4^{4}=256$ residue classes of $(p,q,s,t)$ . Valid canonical representatives use terminal cycle lengths in $\{3,4,5,6\}$ and central arc lengths in $\{1,2,3,4\}$ , replacing the invalid pair $(1,1)$ by $(1,5)$ .

Reversing the orientation of the central cycle gives the arc-swap isomorphism $T(p,q;s,t)\cong T(q,p;t,s)$ , which interchanges the two central arcs ( $s\leftrightarrow t$ ) and the two terminal cycles ( $p\leftrightarrow q$ ). Since the census ranges over all $256$ ordered residue tuples, both orientations of each graph are enumerated; the arc-swap image of the excluded arc-residue pair $(1,1)$ is already present, so replacing its single invalid representative $(s,t)=(1,1)$ by $(s,t)=(1,5)$ removes no residue class.

Two independent exact implementations were used. The first computes the integer characteristic polynomial and counts root signs with rational isolating intervals, including multiplicity. The second uses exact rational symmetric-congruence elimination and does not compute eigenvalues or characteristic polynomials. Both routes agree on every class.

Exactly two oriented residue classes have signature two:

(1,1,1,3)\quad\text{and}\quad(1,1,3,1)\pmod{4}.

The remaining 254 classes have signature at most one. The complete signature distribution is given in Table 1. ∎

Table 1: Exact signature distribution among the 256 residue classes.

Signature	$-4$	$-3$	$-2$	$-1$	$0$	$1$	$2$
Number of classes	2	20	70	78	54	30	2

Corollary 9.3 (Computer-assisted exact class-restricted minimality).

Within the three-cycle-chain class, $G_{0}=T(5,5;1,3)$ is, up to isomorphism, the unique counterexample of minimum order and minimum size.

Proof.

The premise is the computer-assisted exact classification in Theorem 9.2. The smallest cycle length at least three congruent to one modulo four is five, and the smallest positive unordered arc pair with residues one and three is $\{1,3\}$ . Hence every counterexample in the class has at least $5+5+1+3=14$ vertices and at least $16$ edges. Equality forces the parameters of $G_{0}$ . Cycle rotations and reflection of the central cycle show uniqueness up to isomorphism. ∎

10 Reproducibility

The exact materials include:

•

the seed edge list, graph6 encoding, full line-graph adjacency matrix, characteristic polynomial, and rational root certificates;
•

a first-principles implementation of the rooted-module block formula;
•

the exact $11\times 11$ amplifier matrix, rational congruence pivots, inverse-diagonal witness, and deterministic host-attachment tests;
•

direct exact checks of $F_{k}$ for several values of $k$ ;
•

independent Wolfram Language checks of the module and family;
•

the explicit integral four-subdivision transformation and symbolic verification of its block identity;
•

two independent exact implementations of the 256-class residue classification, a committed complete JSON certificate, and a deterministic rowwise comparison;
•

cryptographic checksums and a machine-readable claim ledger.

The computer-assisted classification is finite and deterministic. The unboundedness theorem itself does not depend on extrapolating numerical data: it follows from the general rooted-module congruence and the exact finite certificate for one module.

Generative-AI models accessed through commercial AI services were used in a supporting role for exploratory analysis, code development and checking, literature triage, and adversarial review. Their outputs were not treated as mathematical evidence. The results reported here rest on the explicit proofs, exact certificates, and reproducible computations described above. Details of the services, model families, and verification procedures are recorded in the project documentation.

11 Discussion

The family $F_{k}$ shows that Conjecture 4.12 cannot be repaired by replacing the constant one with any universal constant, even on connected simple planar subcubic cactus graphs. The line-graph signature grows linearly while the root graph remains sparse:

|E(F_{k})|-|V(F_{k})|=2k.

The rooted-module lemma provides a general design principle. Any rooted module with invertible line-graph matrix, zero inverse root diagonal, and positive signature acts as a signature amplifier. The vanishing of the distinguished inverse diagonal entry is related to the literature on singular vertex-deleted principal submatrices and inverse adjacency matrices; NSSD graphs constitute the stronger case in which every inverse diagonal entry vanishes [4]. The contribution here is not the inverse-diagonal phenomenon in the abstract, nor the Schur-complement mechanism, but the explicit rooted $C_{4}$ – $C_{5}$ line-graph module realizing $\operatorname{In}(K)=(6,0,5)$ with zero inverse root diagonal and its use as a signature amplifier on an arbitrary host. The module used here is one explicit realization. Classifying such modules or finding smaller amplifiers is a separate problem.

The four-subdivision theorem reveals a different form of stability. It adds two hyperbolic planes to the integral adjacency form and therefore preserves both the real signature and arithmetic data. This explains why the residue classes modulo four govern the three-cycle-chain classification.

Global minimality of the seed remains open in the present project. The original exhaustive search excludes root graphs of order at most nine, but orders ten through thirteen have not yet been eliminated by a certified global enumeration. Corollary 9.3 is deliberately restricted to the three-cycle-chain class and remains computer-assisted exact because it depends on Theorem 9.2.

The rooted-tree and 2-core reduction programme is maintained as a separate companion-paper research track and is not integrated into this manuscript. In particular, the universal cyclomatic bound and the universal 2-core reduction remain open.

Finally, mathematical validity and historical novelty are distinct. A targeted search located the internal-path inertia reduction of Ma, Yang, and Li [9] and the line-graph signature results of Wang and Fan [11]. The exact rooted-module formulation, four-subdivision congruence, and restricted unbounded family require further specialist review before any historical priority claim is made. No identical public result was identified in the searches completed by 23 July 2026; specialist review remains required, and absence from those searches is not evidence that no prior result exists.

License

Author information

Andrea Paone, independent researcher, Italy. ORCID: 0009-0003-6194-948X. Correspondence: [email protected].

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

During the research and preparation of this work, the author used OpenAI ChatGPT and Codex, and Anthropic Claude accessed through Claude Code, for research assistance, code development and checking, literature triage, adversarial review, and manuscript editing. Outputs incorporated into the work were reviewed, tested, or checked against the relevant proofs, sources, and exact computations, as appropriate, and revised by the author, who takes full responsibility for the content of the article. Generative-AI systems were not credited as authors and were not treated as sources of mathematical authority.

References

[1] S. Akbari, C. Elphick, H. Kumar, S. Pragada, and Q. Tang (2026) A new conjecture on the inertia of graphs. Discrete Mathematics 349 (4), pp. 114953. External Links: Document, 2508.01163, Link Cited by: §1, §1.
[2] H. Chen and J. Li (2026) Counterexamples to a conjecture on graph inertia. External Links: 2605.07196, Document, Link Cited by: §1.
[3] Y. Fan, K. Zhang, and W. Wang (2026) Smith normal forms for coalescences at cospectral vertices. External Links: 2606.08449, Document, Link Cited by: §1.
[4] A. Farrugia, J. B. Gauci, and I. Sciriha (2013) On the inverse of the adjacency matrix of a graph. Special Matrices 1, pp. 28–41. External Links: Document, Link Cited by: §11.
[5] L. Francis and T. Uptain (2026) The signature of connected line graphs is unbounded. External Links: 2607.22874, Document, Link Cited by: §1.
[6] C. He and H. Shan (2019) The signature of two generalizations of line graphs. Linear Algebra and its Applications 575, pp. 159–173. External Links: Document, Link Cited by: §1.
[7] S. R. Jog and R. Kotambari (2016) On the adjacency, laplacian, and signless laplacian spectrum of coalescence of complete graphs. Journal of Mathematics, pp. Article 5906801. External Links: Document, Link Cited by: §1.
[8] H. Ma and C. Xie (2019) The inertia indexes of one special kind of tricyclic graphs. Applied Mathematics 10 (1), pp. 11–18. External Links: Document, Link Cited by: §1.
[9] H. Ma, W. Yang, and S. Li (2013) Positive and negative inertia index of a graph. Linear Algebra and its Applications 438 (1), pp. 331–341. External Links: Document, Link Cited by: §1, §11, §7.
[10] A. Paone (2026) A counterexample to a line-graph inertia conjecture. Zenodo. Note: Version 1.0 External Links: Document, Link Cited by: §1.
[11] L. Wang and Y. Fan (2014) The signature of line graphs and power trees. Linear Algebra and its Applications 448, pp. 264–273. External Links: Document, 1310.1003, Link Cited by: §1, §11, §7.

Unbounded Signature of Line Graphs: Counterexamples and Transfer Principles

Abstract

1 Introduction

2 Preliminaries

Lemma 2.1 (Symmetric Schur elimination).

3 The seed counterexample

4 Rooted-module attachment

Definition 4.1.

Theorem 4.2 (Rooted-module attachment).

Proof.

Corollary 4.3.

5 A signature amplifier

Proposition 5.1 (Amplifier certificate).

Proof.

Corollary 5.2 (One-step amplification).

6 Unbounded signature on a restricted graph class

Definition 6.1.

Theorem 6.2 (Unbounded signature).

Proof.

Corollary 6.3.

Proof.

7 Four-subdivision transfer and prior period-four reduction

Definition 7.1.

Theorem 7.2 (Four-subdivision transfer).

Proof.

Corollary 7.3.

Proof.

Corollary 7.4 (Modulo-four reduction).

8 Fixed-signature families

Theorem 8.1.

Proof.

9 Exact classification of three-cycle chains

Definition 9.1.

Theorem 9.2 (Computer-assisted exact classification).

Exact finite certificate.

Corollary 9.3 (Computer-assisted exact class-restricted minimality).

Proof.

10 Reproducibility

11 Discussion

License

Author information

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

References

Unbounded Signature of Line Graphs:
Counterexamples and Transfer Principles