Response Protection for Line-Graph Equality Families
Transfer under Edge Subdivision and Rooted Attachment

Andrea Paone Marco Paone

(Version 1.0 — 4 August 2026
Preprint; not peer reviewed
DOI: 10.5281/zenodo.21793638)

Abstract

Let $L(G)$ denote the line graph of a connected graph $G$ , and let $c(G)=|E(G)|-|V(G)|+1$ be its cyclomatic number. Motivated by the open bound

2\,\operatorname{sig}(L(G))\leq c(G)+1,

we study how the line-graph signature changes when a missing edge is added. Using the rank-one edge-response criterion for $M(G)=Q(G)-2I$ , we formulate a four-inequality condition that prevents the relevant quadratic response from crossing the threshold at which an edge addition can increase the signature. The rank-one criterion and this threshold have direct antecedents; the new question addressed here is whether a closed family of response bounds survives natural graph operations.

We prove that the condition is preserved by two graph operations: replacing an arbitrary edge by a path with four new internal vertices, and attaching a rooted $C_{4}$ – $C_{5}$ module at an arbitrary vertex. Starting from $C_{5}$ , the operations generate an infinite class of connected planar cactus graphs. If $k$ rooted modules and $r$ four-subdivisions are used, then

\operatorname{In}(L(G))=(6k+2r+3,0,5k+2r+2),\qquad\operatorname{sig}(L(G))=k+1,

and $c(G)=2k+1$ , so every member attains $2\operatorname{sig}(L(G))=c(G)+1$ . As consequences, every one-edge extension satisfies the same bound, and a further general rank-one step gives the corresponding two-edge corollary. The transfer proofs combine Schur complements with finite exact local checks. The response condition is sufficient rather than known to be necessary, and the universal cyclomatic bound remains open.

Keywords: graph inertia; line graph; graph signature; signless Laplacian; cactus graph; edge subdivision; Schur complement.

MSC 2020: 05C50; 15A18.

1 Introduction

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

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

Akbari, Elphick, Kumar, Pragada, and Tang conjectured that every connected line graph has signature at most one [1]. That conjecture is false: one construction gives a $14$ -vertex cactus whose line graph has inertia $(9,0,7)$ , and later constructions show that the signature is unbounded [4, 2]. Those results leave a different extremal question. Can the cyclomatic number

c(G)=|E(G)|-|V(G)|+1

control the signature of $L(G)$ ?

The sharp candidate considered here is

2\,\operatorname{sig}(L(G))\leq c(G)+1.

(1)

It remains open for arbitrary connected graphs. The conjecture, its fixed- cyclomatic extremal formulation, and a one-port protection phenomenon for pendant attachments were developed in our earlier companion paper [5]. That work studies pendant-forest reduction, $2$ -core obstructions, and a rooted response threshold of $-1/2$ . The present paper is not a revision of that companion: it treats the different operation of adding a missing edge within one graph, whose pair-response threshold is $-1$ , and proves preservation results not contained there.

This paper addresses a more specific problem: identify equality graphs for (1) that are stable under natural graph operations and under small edge perturbations. The key observation is that adding a missing edge is a rank-one update of $Q(G)-2I$ . A single quadratic form therefore decides whether the line-graph signature falls, stays fixed, or rises. This mechanism is not new. Francis and Uptain’s Bridge Lemma treats an edge joining two disjoint graphs using the same shifted inverse and the same threshold $-1$ ; their Theorem 5 iterates the criterion along a chain through the Sherman–Morrison formula [2]. For two vertices of one graph, the pair response also contains cross terms.

We formulate a response condition consisting of four lower bounds for this quadratic form. The condition has two roles. First, it excludes the response regime in which one new edge increases the signature. Second, its auxiliary inequalities are strong enough to survive the two operations that generate the families studied here. The proposed new content is not the rank-one threshold, but the closed four-inequality system and its preservation under both operations. The main results are as follows.

(i)

Response protection is preserved when any edge is subdivided four times.
(ii)

It is preserved when a rooted $C_{4}$ – $C_{5}$ module is attached at any vertex.
(iii)

Starting from $C_{5}$ , arbitrary interleavings of these operations give an infinite, branching class of planar cactus graphs satisfying equality in (1).

Every one-edge extension of a graph in this class satisfies (1). Applying the general one-step rank-one bound once more gives a two-edge corollary; this second statement is a consequence, not a separate transfer mechanism.

The period-four behaviour of inertia along paths has antecedents in work of Ma, Yang, and Li and in Wang and Fan’s study of line-graph signatures [3, 13]. Edge addition has also been studied as a spectral perturbation of the signless Laplacian [14], while inverse and Moore–Penrose inverse formulas for signless Laplacians are known for several graph classes [9]. Francis and Uptain give the closest direct response antecedent: their disjoint-bridge criterion uses diagonal entries of $(Q-2I)^{-1}$ and the same threshold, while their chain theorem propagates the boundary response [2]. Our use of inverse quadratic responses is narrower in one direction and broader in another: it is tied to the threshold $2$ for line graphs, but it treats arbitrary vertex pairs in one graph and seeks a four-inequality system closed under two specific operations.

The proofs are organised so that the general algebra is visible before the finite exact obligations. Section 2 derives the response trichotomy. Section 3 motivates and defines response protection. Sections 4 and 5 prove the two transfer theorems, and Sections 6 and 7 give the equality family and edge-extension consequences. The exact finite checks and their independent implementation are described in Section 8; limitations and open questions are stated in Section 10.

2 The response mechanism for an added edge

Throughout, graphs are finite and simple. Unless stated otherwise, they are connected. Let $B$ be the unsigned vertex-edge incidence matrix of a graph $G$ . Then

B^{\mathsf{T}}B=A(L(G))+2I,\qquad BB^{\mathsf{T}}=Q(G),

(2)

where $Q(G)=D(G)+A(G)$ is the signless Laplacian. Put

M(G)=Q(G)-2I.

Lemma 2.1 (Line-graph inertia from $M(G)$ ).

Let $G$ be connected, and let $\operatorname{In}(M(G))=(p,z,n)$ . Then

\operatorname{In}(L(G))=\bigl{(}p,z,n+c(G)-1\bigr{)},\qquad\operatorname{sig}(% L(G))=\operatorname{sig}(M(G))-c(G)+1.

(3)

Proof.

Let $\beta=\dim\ker Q(G)$ . For a connected graph, $\beta=1$ when $G$ is bipartite and $\beta=0$ otherwise. The unsigned incidence matrix therefore has rank $|V(G)|-\beta$ . The nonzero spectra of $B^{\mathsf{T}}B$ and $BB^{\mathsf{T}}=Q(G)$ agree with multiplicity. Hence $B^{\mathsf{T}}B$ has $|E(G)|-|V(G)|+\beta$ zero eigenvalues, whereas $Q(G)$ has $\beta$ zero eigenvalues. After subtracting $2I$ , both sets of zero eigenvalues become $-2$ eigenvalues. Thus $A(L(G))$ has

(|E(G)|-|V(G)|+\beta)-\beta=c(G)-1

additional negative eigenvalues relative to $M(G)$ , while the positive and zero indices are unchanged. This proves (3) in both the bipartite and non-bipartite cases. ∎

Let $u$ and $v$ be nonadjacent vertices of $G$ , and let $b=e_{u}+e_{v}$ . Adding the edge $u v$ changes the signless Laplacian by

M(G+uv)=M(G)+bb^{\mathsf{T}}.

(4)

Figure 1: Adding a missing edge is a rank-one update. The scalar

\alpha_{uv}

determines the resulting change in the line-graph signature.

The scalar $\alpha$ is a zero-energy response of the pair $u, v$ for the shifted signless Laplacian. The threshold is not arbitrary: the value $1+\alpha=0$ is exactly the point at which the rank-one update changes its inertia branch. Rank-one response criteria of this kind are standard; the disjoint-bridge form at the same threshold appears explicitly in Francis and Uptain’s Bridge Lemma [2].

Lemma 2.2 (Exact response trichotomy).

Let $G$ be connected, let $u v$ be a missing edge, and assume that $M=M(G)$ is nonsingular. Set

\alpha=b^{\mathsf{T}}M^{-1}b.

Then adding $u v$ changes the line-graph signature by

\operatorname{sig}(L(G+uv))-\operatorname{sig}(L(G))=\begin{cases}-1,&1+\alpha% >0,\\ 0,&1+\alpha=0,\\ +1,&1+\alpha<0.\end{cases}

(5)

Proof.

Consider the bordered matrix

S=\begin{pmatrix}M&b\\ b^{\mathsf{T}}&-1\end{pmatrix}.

Eliminating the scalar block $-1$ gives $S\sim(M+bb^{\mathsf{T}})\oplus[-1]$ . Eliminating $M$ gives $S\sim M\oplus[-(1+\alpha)]$ . Comparing the two inertias yields the three possible inertias of $M+bb^{\mathsf{T}}$ . Since the cyclomatic number increases by one, lemma 2.1 gives (5). ∎

Remark 2.3 (Relation to the bridge lemma).

Francis and Uptain’s Lemma 4 considers $G_{1}\cup G_{2}+uv$ with $G_{1}$ and $G_{2}$ disjoint. Their condition is

\varphi_{G_{1}}(u)+\varphi_{G_{2}}(v)>-1,\qquad\varphi_{H}(x)=((Q(H)-2I)^{-1})% _{xx}.

Because $(Q(G_{1})\oplus Q(G_{2})-2I)^{-1}$ is block diagonal, the cross terms vanish. Their Theorem 5 then propagates a positive boundary response along a chain using the Sherman–Morrison formula [2]. Lemma 2.2 records the corresponding within-graph pair statement, where $q_{G}(e_{u}+e_{v})$ includes the cross terms. The proposed new content is not the rank-one threshold; it is the four-inequality closed invariant introduced below and the two theorems proving its preservation.

Lemma 2.4 (Universal one-step upper change).

For every connected graph $H$ and every missing edge $e$ ,

\operatorname{sig}(L(H+e))\leq\operatorname{sig}(L(H))+1.

Proof.

A positive semidefinite rank-one update can increase the positive inertia index by at most one and decrease the negative inertia index by at most one; only one eigenvalue can cross zero. Hence the signature of $M(H)$ increases by at most two. The cyclomatic correction in lemma 2.1 increases by one, so the line-graph signature increases by at most one. ∎

3 Response protection

For a graph with nonsingular $M(G)$ , define the quadratic response

q_{G}(x)=x^{\mathsf{T}}M(G)^{-1}x.

A lower bound only for $q_{G}(e_{u}+e_{v})$ would protect one edge addition, but it would not be stable under the transfer formulas used below. The diagonal, difference, and existing-edge bounds in the next definition provide exactly the additional demand types created when old and new vertices are coupled. Thus the definition is designed as a closed family of inequalities rather than as four unrelated estimates.

Definition 3.1 (Response-protected graph).

A connected graph $G$ is response protected if $M(G)$ is nonsingular and the following four inequalities hold:

$\displaystyle\mathrm{P}_{0}$	$\displaystyle:\quad q_{G}(e_{v})\geq-\tfrac{1}{4}$	$\displaystyle\text{for every }v\in V(G),$	(6)
$\displaystyle\mathrm{P}_{+}$	$\displaystyle:\quad q_{G}(e_{u}+e_{v})\geq-1$	$\displaystyle\text{for all distinct }u,v,$	(7)
$\displaystyle\mathrm{P}_{-}$	$\displaystyle:\quad q_{G}(e_{u}-e_{v})\geq-1$	$\displaystyle\text{for all distinct }u,v,$	(8)
$\displaystyle\mathrm{P}_{E}$	$\displaystyle:\quad q_{G}(e_{u}+e_{v})\geq 1$	$\displaystyle\text{for every }uv\in E(G).$	(9)

Condition $\mathrm{P}_{+}$ immediately gives $\alpha\geq-1$ for every missing edge. By lemma 2.2, no single edge addition to a protected graph can increase its line-graph signature. The other three inequalities are the auxiliary conditions needed to preserve $\mathrm{P}_{+}$ under the operations below.

Figure 2: The base graph and the two operations under which response protection is proved to be closed. The root bridge joins the host vertex

v

to the bridge endpoint

a_{0}

on the

C_{4}

component.

Proposition 3.2.

The cycle $C_{5}$ is response protected. Moreover,

\operatorname{In}(M(C_{5}))=(3,0,2),\qquad\det M(C_{5})=2,\qquad\operatorname{% sig}(L(C_{5}))=1.

Proof.

Every vertex of $C_{5}$ has degree two, so $M(C_{5})=A(C_{5})$ . With the cyclic ordering $0,1,2,3,4$ ,

M(C_{5})^{-1}=\frac{1}{2}\begin{pmatrix}1&1&-1&-1&1\\ 1&1&1&-1&-1\\ -1&1&1&1&-1\\ -1&-1&1&1&1\\ 1&-1&-1&1&1\end{pmatrix}.

The diagonal responses are $1/2$ ; edge sums have response $2$ ; nonedge sums and all pair differences have minimum zero. Thus (6)–(9) hold. The inertia and determinant follow directly, and $L(C_{5})\cong C_{5}$ . ∎

4 Transfer under four-subdivision

Let $xy\in E(G)$ . A four-subdivision replaces $x y$ by the path

x-a-b-c-d-y,

introducing four new vertices. Denote the resulting graph by $S_{4}(G,xy)$ .

Theorem 4.1 (Four-subdivision preserves response protection).

If $G$ is response protected, then $S_{4}(G,xy)$ is response protected for every edge $x y$ .

Proof idea.

The four new vertices form an invertible path block. Eliminating this block recovers $M(G)$ exactly, so nonsingularity and inertia are immediate. The inverse formula maps each demand involving a new vertex to one of the four demand types already controlled by response protection. Only finitely many local combinations remain.

Proof.

Write $M=M(G)$ and order the vertices of $S_{4}(G,xy)$ by the old vertices followed by $a, b, c, d$ . The new matrix has block form

M^{\prime}=\begin{pmatrix}M-E_{xy}&C\\ C^{\mathsf{T}}&D\end{pmatrix},

(10)

where $E_{xy}$ has ones in positions $x y$ and $y x$ ,

C=\begin{pmatrix}e_{x}&0&0&e_{y}\end{pmatrix},\qquad D=A(P_{4})=\begin{pmatrix% }0&1&0&0\\ 1&0&1&0\\ 0&1&0&1\\ 0&0&1&0\end{pmatrix}.

The inverse of $D$ is

D^{-1}=\begin{pmatrix}0&1&0&-1\\ 1&0&0&0\\ 0&0&0&1\\ -1&0&1&0\end{pmatrix}.

(11)

Since $CD^{-1}C^{\mathsf{T}}=-E_{xy}$ , the Schur complement of $D$ in (10) is exactly $M$ . Therefore

M^{\prime}\sim M\oplus D.

(12)

For old and new demand vectors $r$ and $s$ , block inversion gives

q_{S_{4}(G,xy)}(r,s)=q_{G}\bigl{(}r-CD^{-1}s\bigr{)}+s^{\mathsf{T}}D^{-1}s.

(13)

The four columns of $CD^{-1}$ are

-e_{y},\quad e_{x},\quad e_{y},\quad-e_{x}.

(14)

Hence every transformed old demand occurring in (6)–(9) is one of

0,\quad\pm e_{t},\quad\pm 2e_{t},\quad\pm e_{u}\pm e_{v}.

The lower bounds for these forms are supplied respectively by zero, $\mathrm{P}_{0}$ , four times $\mathrm{P}_{0}$ , $\mathrm{P}_{+}$ , $\mathrm{P}_{-}$ , or $\mathrm{P}_{E}$ when the pair is $x y$ . Substitution in (13) gives the summary of the exact local enumeration below. The enumeration is exhaustive because every demand is supported on at most two vertices: old–old demands are inherited, while every remaining demand is old–new or new–new. For $\mathrm{P}_{E}$ , the old edges other than $x y$ are inherited and the only new edge demands are the five edges of the replacement path.

Condition	New local cases	Required lower bound	Minimum obtained
$\mathrm{P}_{0}$	4	$-1/4$	$-1/4$
$\mathrm{P}_{+}$	18	$-1$	$-1$
$\mathrm{P}_{-}$	18	$-1$	$-1$
$\mathrm{P}_{E}$	5	$1$	$1$

For example, the internal edge $a b$ transforms to $-e_{x}+e_{y}$ and contributes $2$ from $D^{-1}$ , so its edge response is at least $-1+2=1$ . The first path edge $x a$ transforms to $e_{x}+e_{y}$ , whose response is at least one by $\mathrm{P}_{E}$ for the removed edge $x y$ . The remaining rows follow directly from (11)–(14); the complete row-level enumeration is reproduced by both exact implementations in the accompanying package. Thus all four protected inequalities hold for $M^{\prime}$ . ∎

Corollary 4.2.

A four-subdivision preserves the cyclomatic number and determinant of $M(G)$ , and changes its inertia by $(2,0,2)$ .

Proof.

The matrix $D=A(P_{4})$ has determinant one and inertia $(2,0,2)$ . Apply (12). A four-subdivision adds four vertices and four edges, so $c(G)$ is unchanged. ∎

5 Transfer under rooted amplifier attachment

Let $\mathcal{A}$ be the following rooted attachment. Add a new $4$ -cycle $a_{0}a_{1}a_{2}a_{3}a_{0}$ , a new $5$ -cycle $b_{0}b_{1}b_{2}b_{3}b_{4}b_{0}$ , the bridge $a_{1}b_{0}$ , and the bridge $va_{0}$ from an arbitrary host vertex $v$ . The nine new vertices are ordered as

a_{0},a_{1},a_{2},a_{3},b_{0},b_{1},b_{2},b_{3},b_{4}.

Theorem 5.1 (Amplifier attachment preserves response protection).

If $G$ is response protected, then attaching $\mathcal{A}$ at any vertex $v\in V(G)$ produces a response-protected graph.

Proof idea.

The rooted module has a boundary response equal to one. Its contribution to the old host diagonal is therefore cancelled exactly by the degree change at the attachment vertex. The enlarged matrix is congruent to a direct sum, and the boundary row of the module inverse reduces every new demand to a protected old demand with coefficient at most two.

Proof.

Let $M=M(G)$ and $e=e_{v}$ . In the stated ordering, the new-vertex block $K$ is shown in appendix B. Direct exact calculation gives

\det K=-2,\qquad\operatorname{In}(K)=(6,0,3),

(15)

and

e_{0}^{\mathsf{T}}K^{-1}=(1,0,-1,0,0,0,0,0,0),\qquad(K^{-1})_{00}=1.

(16)

The matrix of the enlarged graph is

M^{\prime}=\begin{pmatrix}M+ee^{\mathsf{T}}&ee_{0}^{\mathsf{T}}\\ e_{0}e^{\mathsf{T}}&K\end{pmatrix}.

(17)

The Schur complement of $K$ is

M+ee^{\mathsf{T}}-e(e_{0}^{\mathsf{T}}K^{-1}e_{0})e^{\mathsf{T}}=M.

Consequently

M^{\prime}\sim M\oplus K.

(18)

If $r$ is an old demand and $s$ a demand on the nine new vertices, then

q_{G^{\prime}}(r,s)=q_{G}\bigl{(}r-e(e_{0}^{\mathsf{T}}K^{-1}s)\bigr{)}+s^{% \mathsf{T}}K^{-1}s.

(19)

By (16), the old correction is an integer multiple of $e_{v}$ . For the demands relevant to $\mathrm{P}_{0}$ – $\mathrm{P}_{E}$ , its coefficient lies in $\{-2,-1,0,1,2\}$ . Every old term is therefore controlled by $\mathrm{P}_{0}$ , $\mathrm{P}_{+}$ , or $\mathrm{P}_{-}$ . Exact substitution of the displayed $K^{-1}$ gives:

Condition	New local cases	Required lower bound	Minimum obtained
$\mathrm{P}_{0}$	9	$-1/4$	$1/2$
$\mathrm{P}_{+}$	54	$-1$	$0$
$\mathrm{P}_{-}$	54	$-1$	$0$
$\mathrm{P}_{E}$	11	$1$	$1$

Here the $11$ edge cases are the root bridge $va_{0}$ , the four cycle edges of $C_{4}$ , the five cycle edges of $C_{5}$ , and the bridge $a_{1}b_{0}$ . The enumeration is exhaustive for the same support reason: old–old demands and old edges are inherited, while every remaining demand is host–new, generic old–new, or new–new; the edge list is exactly the root bridge and the ten module edges. The table is a finite rational calculation from (19); the full $K^{-1}$ and the complete independent enumeration are included in the accompanying package. Thus all four protected inequalities are preserved. ∎

Corollary 5.2.

Each amplifier attachment adds nine vertices and eleven edges, increases the cyclomatic number by two, multiplies $\det M(G)$ by $-2$ , and adds $(6,0,3)$ to the inertia of $M(G)$ .

Proof.

Use (18) and (15). The graph operation adds nine vertices and eleven edges. ∎

6 The generated equality class

Let $\mathcal{C}$ be the smallest class containing $C_{5}$ and closed under:

(i)

attachment of $\mathcal{A}$ at any current vertex; and
(ii)

four-subdivision of any current edge.

The operations may be interleaved, modules may branch, and several modules may be attached at the same host vertex. Every graph in $\mathcal{C}$ is connected, simple, non-bipartite, planar, and a cactus graph.

Figure 3: A branching member of

\mathcal{C}

obtained by attaching two amplifiers at different vertices of the base cycle. Further modules may be attached at any existing vertex, and any edge may be four-subdivided.

Theorem 6.1 (Protected equality family).

Let $G\in\mathcal{C}$ be obtained using $k$ amplifier attachments and $r$ four-subdivisions. Then $G$ is response protected and

$\displaystyle\|V(G)\|$	$\displaystyle=5+9k+4r,$	$\displaystyle\|E(G)\|$	$\displaystyle=5+11k+4r,$	(20)
$\displaystyle c(G)$	$\displaystyle=2k+1,$	$\displaystyle\det M(G)$	$\displaystyle=2(-2)^{k},$	(21)
$\displaystyle\operatorname{In}(M(G))$	$\displaystyle=(6k+2r+3,0,3k+2r+2).$			(22)

Moreover,

\operatorname{In}(L(G))=(6k+2r+3,0,5k+2r+2),\qquad\operatorname{sig}(L(G))=k+1,

(23)

2\operatorname{sig}(L(G))=c(G)+1,\qquad\det A(L(G))=2(-8)^{k}.

(24)

Proof idea.

Each operation has an additive inertia contribution and a transparent effect on $|V|$ , $|E|$ , and the determinant. The formulas therefore depend only on the number of operations, not on their order or attachment locations.

Proof.

The base graph $C_{5}$ is protected by proposition 3.2. Protection is preserved by theorems 4.1 and 5.1. The size, cyclomatic number, determinant, and inertia formulas follow inductively from corollaries 4.2 and 5.2.

Because every member contains an odd cycle, lemma 2.1 applies. Here $c(G)-1=2k$ , so adding the $2k$ surplus negative eigenvalues to (22) gives (23). The signature and equality in (24) follow. Finally, the incidence relation gives

\det A(L(G))=(-2)^{c(G)-1}\det M(G)=(-2)^{2k}\,2(-2)^{k}=2(-8)^{k}.

∎

The alternating chain $C_{5},(C_{4},C_{5})^{k}$ from [4] is one subfamily. The closure theorem is broader: the amplifiers need not form a chain, and four-subdivisions may be placed on any edge created at any stage.

7 Edge-extension consequences

Proposition 7.1 (One-edge extension protection).

Let $G\in\mathcal{C}$ . For every missing edge $e$ , the graph $G+e$ satisfies (1).

Proof.

Write $s=\operatorname{sig}(L(G))$ and $c=c(G)$ . By theorem 6.1, $2s=c+1$ . Since $G$ is protected, $\mathrm{P}_{+}$ and lemma 2.2 imply

\operatorname{sig}(L(G+e))\leq s.

The new cyclomatic number is $c+1$ , hence

2\operatorname{sig}(L(G+e))\leq 2s=c+1<c+2=c(G+e)+1.

∎

Corollary 7.2 (Two-edge extension).

Let $G\in\mathcal{C}$ , and let $e, f$ be distinct missing edges whose addition gives a simple graph. Then $G+e+f$ satisfies (1).

Proof.

By proposition 7.1, $\operatorname{sig}(L(G+e))\leq\operatorname{sig}(L(G))$ . The universal bound in lemma 2.4 applies to the second update regardless of whether $G+e$ remains response protected. If $s=\operatorname{sig}(L(G))$ and $c=c(G)$ , then

\operatorname{sig}(L(G+e+f))\leq\operatorname{sig}(L(G+e))+1\leq s+1.

Since $2s=c+1$ and $c(G+e+f)=c+2$ ,

2\operatorname{sig}(L(G+e+f))\leq 2s+2=c+3=c(G+e+f)+1.

∎

The two-edge statement is therefore an immediate second-step consequence of the one-edge protection and the general rank-one estimate. It is not an independent preservation theorem. The argument supplies no comparable bound from the third added edge onward.

8 Computer-assisted verification of the finite obligations

The transfer theorems are algebraic statements. Computation enters only after the Schur complements have reduced each proof to a finite list of local demand vectors. The proof dependence is therefore:

\text{block identity}\;+\;\text{complete local enumeration}\;\Longrightarrow\;% \text{transfer theorem}.

The larger graph searches described in the reproducibility package are regressions and discovery evidence; they are not premises of the theorems.

Two implementations enumerate the local obligations independently. The primary implementation uses exact symbolic matrices. The second uses only fractions.Fraction, explicit matrix multiplication, and a separate case generator. They agree on the number of cases and on the sharp lower bounds:

Operation	$\mathrm{P}_{0}$	$\mathrm{P}_{+}$	$\mathrm{P}_{-}$	$\mathrm{P}_{E}$
Four-subdivision	$-1/4$	$-1$	$-1$	$1$
Amplifier attachment	$1/2$	$0$	$0$	$1$

The obligation classes are summarised in table 1. Each class is generated from the displayed inverse block, not from sampled host graphs. Because each protected inequality involves one vertex, a pair of vertices, or an edge, the old–old/old–new/new–new partition used by the generators is exhaustive. The accompanying audit first corrupts selected matrix entries, thresholds, and manuscript constants and confirms that the corresponding checks fail. It then runs the unmodified identities, enumerations, source-to-PDF consistency tests, and exact graph regressions. This self-test guards against a verifier that would report success without reaching its intended target.

As additional regression evidence, a separate graph-atlas test finds $41$ connected response-protected graphs on at most seven vertices, including three bipartite examples, and checks every edge subdivision and every possible amplifier host without a failure. Exhaustive labelled tests also cover all $336$ one- and two-step four-subdivisions of the $C_{5}$ – $C_{4}$ – $C_{5}$ seed and all $75$ one- and two-level labelled amplifier attachments descended from $C_{5}$ . The alternating chain is also checked exactly for $k=0,\ldots,7$ . These finite runs support the implementation but do not enlarge the scope of the symbolic proof.

9 Related work and scope of the contribution

The incidence relation between $Q(G)$ and $A(L(G))$ is classical; see, for example, the signless-Laplacian survey of Cvetković, Rowlinson, and Simić [7]. Wang and Fan used path reductions in their study of line-graph signature [13], building on inertia methods of Ma, Yang, and Li [3]. Bounds involving matching and cyclomatic numbers were developed by Fan and Wang [8]. Yu, Cai, and Fan studied signless-Laplacian spectral perturbations under edge addition and edge contraction [14]. Their interlacing results start from the same rank-one edge update. Classical bordered-matrix and determinant identities then give the three-way inertia branch recorded in lemma 2.2; that lemma is used for exposition and is not claimed as a new perturbation method.

Francis and Uptain’s Lemma 4 is the closest graph-specific antecedent. It joins two disjoint graphs by a bridge and uses the same shifted inverse, the same rank-one update, and the same threshold $-1$ . Their Theorem 5 propagates a positive boundary response along a chain by Sherman–Morrison, and their $14$ -vertex base graph is the same $C_{4}$ – $C_{5}$ – $C_{5}$ cactus appearing as the one-amplifier equality graph here [2]. In their bridge setting the inverse is block diagonal and the cross terms vanish. The present pair condition applies to arbitrary vertices of one graph and therefore keeps the cross terms, but it should be read as an extension of this response framework rather than as its origin.

Inverse and generalized-inverse formulas for signless Laplacians were obtained for trees and odd unicyclic graphs by Hessert and Mallik [9]. The star-complement reconstruction theorem also uses bilinear forms defined by the inverse of a shifted adjacency matrix to control spectral extensions [10]. That framework is an important conceptual antecedent for inverse-response arguments, although it addresses prescribed eigenvalue multiplicity rather than the four lower bounds and graph operations considered here. Rooted attachments and related “pocket” constructions have likewise been analysed through characteristic polynomials and signless-Laplacian coronals [11]. Recent work on subdivision graphs studies signless-Laplacian spectral sums above the threshold $2$ [12]; it does not give the response invariant or the exact signature-transfer statements proved below.

A separate companion preprint computes the complete threshold-two inertia, including singular branches, for arbitrary rose graphs and generalized theta graphs [6]. Its reduction deletes one or two shared vertices and evaluates the resulting path blocks. The overlap with the present paper is limited to the classical incidence transfer, Schur-complement and path algebra, and the degenerate $k=0$ part of our family, where $C_{5}$ and its four-subdivisions are the cycles $C_{5+4r}$ . That preprint does not formulate response protection, prove either preservation theorem, or construct the branching amplifier family. Conversely, the present paper does not give full inertia formulas for arbitrary roses or generalized theta graphs.

The earlier fixed-cyclomatic companion paper introduces the conjectural bound, rooted pendant response, $2$ -core counterexamples, and extremal constructions at fixed cyclomatic number [5]. The present paper uses that programme as motivation but does not repeat its pendant-forest reduction or its one-port threshold. Its distinct claims concern pair responses for missing edges, a closed four-inequality invariant, two preservation theorems, and the resulting branching equality family.

The unbounded line-graph-signature construction, the rooted amplifier’s additive inertia increment, the chain construction, and the integral four-subdivision congruence are inherited or publicly anticipated [4, 2]; they are not new claims of this paper. Nor do we claim the rank-one response criterion or the threshold $-1$ as new. The proposed contribution is the closed four-inequality invariant, its preservation under arbitrary-edge four-subdivision and arbitrary-host amplifier attachment, and the branching equality family that follows. The one-edge proposition follows from this invariant; the two-edge statement is an immediate corollary.

Within the literature reviewed through 4 August 2026, we found no earlier theorem proving simultaneous preservation of these four inequalities under both operations. This is a bounded literature statement, not a claim of absolute historical priority. The closest general frameworks show that the individual ingredients—rank-one perturbation, inverse bilinear forms, Schur complements, rooted attachments, and period-four subdivision phenomena—are established tools. The possible novelty lies in the two preservation theorems and their exact combination, not in the underlying response method.

10 Limitations and open questions

Response protection is a sufficient invariant. It is not known to be necessary for equality in (1), and the class $\mathcal{C}$ is not claimed to contain all equality graphs. The proof also relies on nonsingularity of $M(G)$ . A useful extension would replace the inverse by a range-compatible generalized response and treat singular equality graphs without discarding nullity branches.

The edge-extension consequences are sharp with respect to the present argument. The first edge is controlled by $\mathrm{P}_{+}$ ; a general rank-one estimate controls only one further edge. From the third added edge onward, the current invariant no longer supplies enough information. It remains open whether a stronger multi-edge response condition is preserved by the same operations.

Further questions include whether the four inequalities can be compressed into a standard matrix-cone condition, whether smaller closed systems of inequalities exist, and which other rooted modules preserve response protection. Most importantly, the universal bound (1) remains unresolved.

11 Conclusion

A missing edge changes $Q(G)-2I$ by a rank-one positive semidefinite matrix, and the established inverse-response criterion identifies the branch in which that edge can increase the line-graph signature. The contribution developed here is to close four response bounds under four-subdivision and rooted amplifier attachment. This yields an infinite branching class of equality graphs, a one-edge protection proposition, and the two-edge corollary obtained from one additional general rank-one step. The construction supplies a structured extremal family for the cyclomatic problem, while leaving the universal bound and the classification of all equality graphs open.

Appendix A Finite local obligations

Table 1: Summary of the complete classes of new local demands in the two transfer proofs.

Operation and condition	Demand class	Cases	Minimum
Four-subdivision, $\mathrm{P}_{0}$	One new internal vertex	4	$-1/4$
Four-subdivision, $\mathrm{P}_{+}$	Old–new and new–new sums	18	$-1$
Four-subdivision, $\mathrm{P}_{-}$	Old–new and new–new differences	18	$-1$
Four-subdivision, $\mathrm{P}_{E}$	Five edges of the replacement path	5	$1$
Amplifier, $\mathrm{P}_{0}$	One new module vertex	9	$1/2$
Amplifier, $\mathrm{P}_{+}$	Host–new, generic old–new, and new–new sums	54	$0$
Amplifier, $\mathrm{P}_{-}$	Host–new, generic old–new, and new–new differences	54	$0$
Amplifier, $\mathrm{P}_{E}$	Root bridge and ten internal module edges	11	$1$

The old–old demands are inherited. Every other one- or two-vertex demand is old–new or new–new, so the displayed classes exhaust the four protected inequalities. In the four-subdivision proof the removed edge $x y$ is replaced by the five path edges listed in theorem 4.1. In the amplifier proof the edge demands are exactly the root bridge and ten module edges, and the host degree change is cancelled by the boundary response $(K^{-1})_{00}=1$ . The exact accompanying tables record every demand vector, the old protected inequality used, the constant term from the local inverse, and the resulting lower bound.

Appendix B The amplifier matrices

For the new vertices $a_{0},a_{1},a_{2},a_{3},b_{0},b_{1},b_{2},b_{3},b_{4}$ , the block in (17) is

K=\begin{pmatrix}1&1&0&1&0&0&0&0&0\\ 1&1&1&0&1&0&0&0&0\\ 0&1&0&1&0&0&0&0&0\\ 1&0&1&0&0&0&0&0&0\\ 0&1&0&0&1&1&0&0&1\\ 0&0&0&0&1&0&1&0&0\\ 0&0&0&0&0&1&0&1&0\\ 0&0&0&0&0&0&1&0&1\\ 0&0&0&0&1&0&0&1&0\end{pmatrix}.

Its inverse is

K^{-1}=\begin{pmatrix}1&0&-1&0&0&0&0&0&0\\ 0&\frac{3}{2}&0&-\frac{3}{2}&-\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&\frac{1}{2}% &-\frac{1}{2}\\ -1&0&1&1&0&0&0&0&0\\ 0&-\frac{3}{2}&1&\frac{3}{2}&\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}% &\frac{1}{2}\\ 0&-\frac{1}{2}&0&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}% &\frac{1}{2}\\ 0&-\frac{1}{2}&0&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&% -\frac{1}{2}\\ 0&\frac{1}{2}&0&-\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&% -\frac{1}{2}\\ 0&\frac{1}{2}&0&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&\frac{1}{2}% &\frac{1}{2}\\ 0&-\frac{1}{2}&0&\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}% &\frac{1}{2}\end{pmatrix}.

Multiplication gives $KK^{-1}=I_{9}$ . Exact symmetric congruence gives $\operatorname{In}(K)=(6,0,3)$ , and direct expansion gives $\det K=-2$ .

Appendix C Reproducibility package

An accompanying reproducibility package contains the LaTeX source, exact primary and independent implementations, the full local-case records, labelled graph regressions, environment information, a manifest, and SHA-256 checksums. The main theorems depend on the displayed block algebra and complete finite local enumerations. An additional independent Wolfram Language 15.0 calculation recomputes the base responses, both local inverses and inertias, every finite local minimum, and representative generated-family invariants. Exploratory searches are stored separately and are not used as proof.

Data and code availability

All graphs in the proofs are defined explicitly in the text. The exact code and certificates needed to reproduce the finite obligations accompany this version.

CRediT author statement

Andrea Paone and Marco Paone contributed equally to the conceptualization, methodology, formal analysis, investigation, software, validation, visualization, writing of the original draft, and review and editing of this work. Both authors reviewed and approved the manuscript and accept responsibility for its content.

Funding

This research received no external funding.

Competing interests

The authors declare no competing interests.

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

During the research and preparation of this work, the authors used OpenAI ChatGPT for exploratory analysis of candidate constructions and proof strategies, 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, exact computations, and independent Wolfram Language verification, as appropriate, and revised by the authors, who take full responsibility for the content of the article. The AI system was not credited as an author and was not treated as a source of mathematical authority.

Author information and correspondence

Andrea Paone
Independent Researcher, Italy

ORCID: 0009-0003-6194-948X

Email: [email protected]

Corresponding author.

Marco Paone
Independent Researcher, Italy

ORCID: 0009-0001-6792-879X

Email: [email protected]

Corresponding author.

References

[1] S. Akbari, C. Elphick, H. Kumar, S. Pragada, and Q. Tang, A new conjecture on the inertia of graphs, Discrete Mathematics 349 (2026), no. 4, 114953. doi:10.1016/j.disc.2025.114953.
[2] L. Francis and T. Uptain, The signature of connected line graphs is unbounded, arXiv:2607.22874 (2026). doi:10.48550/arXiv.2607.22874.
[3] H. Ma, W. Yang, and S. Li, Positive and negative inertia index of a graph, Linear Algebra and its Applications 438 (2013), 331–341. doi:10.1016/j.laa.2012.07.014.
[4] A. Paone, Unbounded Signature of Line Graphs: Counterexamples and Transfer Principles, Version 2.0-rev2, Zenodo (2026). doi:10.5281/zenodo.21737348.
[5] A. Paone and M. Paone, Line-Graph Signature Beyond the 2-Core: Exact Counterexamples, Rooted Response, and Extremal Constructions at Fixed Cyclomatic Number, Version 1.3, Zenodo (2026). doi:10.5281/zenodo.21706797.
[6] A. Paone and M. Paone, Line-Graph Inertia of Roses and Generalized Theta Graphs, Version 1.0 preprint, 30 July 2026.
[7] D. Cvetković, P. Rowlinson, and S. K. Simić, Signless Laplacians of finite graphs, Linear Algebra and its Applications 423 (2007), 155–171. doi:10.1016/j.laa.2007.01.009.
[8] Y.-Z. Fan and L. Wang, Bounds for the positive and negative inertia index of a graph, Linear Algebra and its Applications 522 (2017), 15–27. doi:10.1016/j.laa.2017.02.005.
[9] R. Hessert and S. Mallik, Moore–Penrose inverses of the signless Laplacian and edge-Laplacian of graphs, Discrete Mathematics 344 (2021), 112451. doi:10.1016/j.disc.2021.112451.
[10] D. Cvetković, P. Rowlinson, and S. K. Simić, Graphs with least eigenvalue $-2$ : the star complement technique, Journal of Algebraic Combinatorics 14 (2001), 5–16. doi:10.1023/A:1011209801191.
[11] S.-Y. Cui and G.-X. Tian, The spectra and the signless Laplacian spectra of graphs with pockets, Applied Mathematics and Computation 315 (2017), 363–371. doi:10.1016/j.amc.2017.07.056.
[12] Y. Liu and Q. Tang, Path-minimality for positive $p$ -energies, Laplacian-type spectra, and line graphs, arXiv:2606.30996 (2026). doi:10.48550/arXiv.2606.30996.
[13] L. Wang and Y.-Z. Fan, The signature of line graphs and power trees, Linear Algebra and its Applications 448 (2014), 264–273. doi:10.1016/j.laa.2014.01.020.
[14] G.-D. Yu, G.-X. Cai, and Y.-Z. Fan, Some notes on the spectral perturbations of the signless Laplacian of a graph, Applied Mathematics: A Journal of Chinese Universities 29 (2014), 241–248. doi:10.1007/s11766-014-3155-9.

Response Protection for Line-Graph Equality Families Transfer under Edge Subdivision and Rooted Attachment

Abstract

1 Introduction

2 The response mechanism for an added edge

Lemma 2.1 (Line-graph inertia from M⁢(G)).

Proof.

Lemma 2.2 (Exact response trichotomy).

Proof.

Remark 2.3 (Relation to the bridge lemma).

Lemma 2.4 (Universal one-step upper change).

Proof.

3 Response protection

Definition 3.1 (Response-protected graph).

Proposition 3.2.

Proof.

4 Transfer under four-subdivision

Theorem 4.1 (Four-subdivision preserves response protection).

Proof idea.

Proof.

Corollary 4.2.

Proof.

5 Transfer under rooted amplifier attachment

Theorem 5.1 (Amplifier attachment preserves response protection).

Proof idea.

Proof.

Corollary 5.2.

Proof.

6 The generated equality class

Theorem 6.1 (Protected equality family).

Proof idea.

Proof.

7 Edge-extension consequences

Proposition 7.1 (One-edge extension protection).

Proof.

Corollary 7.2 (Two-edge extension).

Proof.

8 Computer-assisted verification of the finite obligations

9 Related work and scope of the contribution

10 Limitations and open questions

11 Conclusion

Appendix A Finite local obligations

Appendix B The amplifier matrices

Appendix C Reproducibility package

Data and code availability

CRediT author statement

Funding

Competing interests

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

Author information and correspondence

References

Response Protection for Line-Graph Equality Families
Transfer under Edge Subdivision and Rooted Attachment

Lemma 2.1 (Line-graph inertia from $M(G)$ ).