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

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 sig(L(G)) ≤ c(G) + 1, the authors 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, they 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. They prove that the condition is preserved by arbitrary-edge four-subdivision and by attaching a rooted C4-C5 module at an arbitrary vertex. Starting from C5, these operations generate an infinite class of connected planar cactus graphs attaining 2 sig(L(G)) = c(G) + 1. Every one-edge extension satisfies the same bound, and a general rank-one step yields a two-edge corollary. The proofs combine Schur complements with complete finite exact local checks. The response condition is sufficient rather than known to be necessary, and the universal cyclomatic bound remains open.