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
Editorial revision 2 — 1 August 2026)

Abstract

Akbari, Elphick, Kumar, Pragada, and Tang conjectured that every connected graph $G$ satisfies $n_{+}(L(G))\leq n_{-}(L(G))+1$ . We prove that the failure of this inequality is unbounded even when $G$ is connected, simple, planar, subcubic, and a cactus. The proof uses a rooted attachment principle: if a rooted module $M$ has invertible line-graph adjacency matrix $K$ and the root-edge diagonal entry of $K^{-1}$ is zero, then attaching $M$ at an arbitrary host vertex adds $\operatorname{In}(K)$ to the line-graph inertia. A rooted $C_{4}$ – $C_{5}$ module has $\operatorname{In}(K)=(6,0,5)$ and determinant $-8$ , and its iteration gives graphs $F_{k}$ with

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

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

We also prove that subdividing an arbitrary edge four times gives an explicit integral unimodular congruence that adds $(2,0,2)$ to the line-graph inertia and preserves the determinant, adjacency cokernel, nonunit Smith invariant factors, and nullity over every field. This yields a modulo-four reduction for subdivision vectors. An exact computer-assisted classification of all $256$ residue classes of three-cycle chains then identifies precisely the two oriented counterexample classes.

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

MSC 2020: 05C50; 15A18.

Editorial revision 2, 1 August 2026. This revision adds schematic figures, makes the seed and amplifier certificates directly checkable from the manuscript, and improves the abstract, reproducibility statement, and discussion. The theorem statements, hypotheses, previously stated formulas, canonical exact outputs, and numerical conclusions are unchanged from Version 2.0-rev1.

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 an isomorphic $14$ -vertex counterexample and proved unboundedness by joining whole copies of that seed through bridges, using a signless-Laplacian resolvent argument. The construction here instead iterates a smaller rooted $C_{4}$ – $C_{5}$ module on arbitrary hosts and produces the alternating cycle family $C_{5},(C_{4},C_{5})^{k}$ . The two papers establish the same global phenomenon through different local mechanisms; no claim of 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}$ .

Figure 1: The seed and the unbounded family. In

G_{0}

the two bridges meet adjacent vertices

5

and

6

of the central square. The lower panel is schematic:

F_{k}

contains

k+1

copies of

C_{5}

and

k

copies of

C_{4}

, with adjacent bridge attachments in every internal cycle.

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)

The sign count is also directly visible from the factorization. Since $A(L(G_{0}))$ is symmetric, every root of $\chi_{0}$ is real. Descartes’ rule of signs applied to the cubic and quintic factors, and to their evaluations at $-x$ , gives the exact contributions in Table 1; none of the factors vanishes at zero.

Table 1: Sign contribution of the factors in (2).

Factor	Positive roots	Negative roots
$x-2$ and $x-1$	2	0
$(x+2)^{2}$	0	2
$(x^{2}+x-1)^{2}$	2	2
$x^{3}-2x^{2}-4x+1$	2	1
$x^{5}-x^{4}-6x^{3}+3x^{2}+7x-2$	3	2
Total	9	7

Consequently,

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

(3)

Exact rational root isolation and exact rational congruence independently confirm the same inertia in the reproducibility package.

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$ .

Figure 2: Rooted attachment. The open root vertex

r

is identified with the host vertex

v

. In the new line graph, the root edge

\rho

is the only edge-vertex of

M

adjacent to old edge-vertices of

H

, and those old edge-vertices are precisely the edges incident 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.

Appendix A displays the ordered matrix $K$ and an explicit rational change-of-basis matrix $T$ with $\det T=-1$ such that

T^{\mathsf{T}}KT=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}$ .

Figure 3: Four-subdivision and the local line-graph path. Here

R_{u}

and

R_{v}

denote the old edge-vertices incident with

u

and

v

, respectively. With the ordering shown, the final four local coordinates induce

J\oplus J

, which is the invertible block eliminated in Theorem 7.2.

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. The canonical output is results/three_cycle_residue_classification.json. Its SHA-256, followed by that of the rowwise comparison, is

f674e3d39241774d1c89101337cbc938927af7167ce2aee964bf36cc5a13b1a4
ac8756eac191036fbd27921e8eb6e2bdd80aec6656a3c069e57a077cb3ab50a2

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 2. ∎

Table 2: 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 version-specific record for this revision is doi:10.5281/zenodo.21737348. Its reproducibility package contains the manuscript source, the exact scripts, the canonical result files, the dependency lock, and checksums for every packaged file.

The principal audit reconstructs from the stated edge lists the seed, the rooted module, the alternating family, the four-subdivision identity, the four-parameter family, and all $256$ three-cycle residue classes. The relevant files are:

•

scripts/run_v2_manuscript_exact_audit.py;
•

results/v2_manuscript_exact_results.json;
•

scripts/classify_three_cycle_chain_residues.py;
•

scripts/classify_three_cycle_chain_residues_congruence.py;
•

scripts/compare_three_cycle_methods.py;
•

scripts/verify_amplifier_displayed_certificate.py.

The two classification scripts are compared row by row. The final script verifies the explicit amplifier basis printed in Appendix A.

All reported computations use exact integer or rational arithmetic, exact polynomial factorization, or rational root isolation; no floating-point threshold is used. The finite classification is computer-assisted exact. The unboundedness theorem is not an extrapolation from the finite computations: it follows from the rooted attachment theorem and the single exact module certificate.

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. The original exhaustive search excludes root graphs of order at most nine, but orders ten through thirteen have not 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.

A general rooted-tree or 2-core reduction lies beyond the scope of this paper; in particular, the universal cyclomatic bound and a universal 2-core reduction remain open.

Mathematical validity and historical novelty are distinct. Ma, Yang, and Li [9] established the internal-path real-inertia reduction, and Wang and Fan [11] used its period-four consequences for line-graph signatures. The claims made here are limited to the explicitly stated rooted-module formula, the displayed integral four-subdivision congruence and its arithmetic consequences, and the restricted families and classification proved above. No claim of absolute historical priority is made.

Appendix A Exact amplifier congruence certificate

Let $e_{1},\ldots,e_{11}$ be the standard basis in the edge order used in Section 5:

\rho,\ x_{0}x_{1},\ x_{1}x_{2},\ x_{2}x_{3},\ x_{3}x_{0},\ x_{1}y_{0},\ y_{0}y% _{1},\ y_{1}y_{2},\ y_{2}y_{3},\ y_{3}y_{4},\ y_{4}y_{0}.

In this basis the line-graph adjacency matrix of the module is

$K=\setcounter{MaxMatrixCols}{11}\begin{pmatrix}0&1&0&0&1&0&0&0&0&0&0\\ 1&0&1&0&1&1&0&0&0&0&0\\ 0&1&0&1&0&1&0&0&0&0&0\\ 0&0&1&0&1&0&0&0&0&0&0\\ 1&1&0&1&0&0&0&0&0&0&0\\ 0&1&1&0&0&0&1&0&0&0&1\\ 0&0&0&0&0&1&0&1&0&0&1\\ 0&0&0&0&0&0&1&0&1&0&0\\ 0&0&0&0&0&0&0&1&0&1&0\\ 0&0&0&0&0&0&0&0&1&0&1\\ 0&0&0&0&0&1&1&0&0&1&0\end{pmatrix}.$

Define $T=(t_{1}\ \cdots\ t_{11})$ by

$\displaystyle t_{1}$	$\displaystyle=e_{1},$	$\displaystyle t_{2}$	$\displaystyle=e_{2},$
$\displaystyle t_{3}$	$\displaystyle=-e_{1}-e_{2}+e_{5},$	$\displaystyle t_{4}$	$\displaystyle=-\tfrac{1}{2}e_{1}-\tfrac{1}{2}e_{2}+e_{4}+\tfrac{1}{2}e_{5},$
$\displaystyle t_{5}$	$\displaystyle=e_{2}+e_{3}-e_{4}-e_{5},$	$\displaystyle t_{6}$	$\displaystyle=-e_{1}+e_{4}+e_{6},$
$\displaystyle t_{7}$	$\displaystyle=-\tfrac{1}{2}e_{2}-\tfrac{1}{2}e_{3}+\tfrac{1}{2}e_{4}+\tfrac{1}% {2}e_{5}+e_{7},$	$\displaystyle t_{8}$	$\displaystyle=e_{8},$
$\displaystyle t_{9}$	$\displaystyle=\tfrac{1}{2}e_{2}+\tfrac{1}{2}e_{3}-\tfrac{1}{2}e_{4}-\tfrac{1}{% 2}e_{5}-e_{7}+e_{9},$	$\displaystyle t_{10}$	$\displaystyle=e_{10},$
$\displaystyle t_{11}$	$\displaystyle=-e_{2}-e_{3}+e_{4}+e_{5}+e_{7}-e_{8}-e_{9}+e_{10}+e_{11}.$

Direct multiplication gives $\det T=-1$ and

T^{\mathsf{T}}KT=\begin{pmatrix}0&1\\ 1&0\end{pmatrix}\oplus[-2]\oplus[1/2]\oplus\begin{pmatrix}0&2\\ 2&0\end{pmatrix}\oplus\begin{pmatrix}0&1\\ 1&0\end{pmatrix}^{\!\oplus 2}\oplus[2],

which is (6). Thus the certificate can be checked using only rational matrix multiplication. The same identity is reproduced by the versioned verification script and JSON certificate in the public package. The JSON certificate has SHA-256

206fc4e97aac109c51c7ceb736b812d043c836ea35d2ef87b12da8d37abba846.

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 through Claude Code for exploratory analysis, software development and checking, literature triage, and manuscript editing. The author reviewed and revised all incorporated output and checked it against the proofs, cited sources, and exact computations as appropriate. The author takes full responsibility for the article. Generative-AI systems were not credited as authors and were not treated as sources of mathematical or scientific 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

Appendix A Exact amplifier congruence certificate

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