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

Abstract

Sia L(G) il line graph di un grafo connesso G e sia c(G) = |E(G)| − |V(G)| + 1 il suo numero ciclomatico. Motivati dal limite aperto 2 sig(L(G)) ≤ c(G) + 1, gli autori studiano come cambia la signature del line graph quando si aggiunge un lato mancante. Usando il criterio di risposta di rango uno per M(G) = Q(G) − 2I, formulano una condizione di quattro disuguaglianze che impedisce alla risposta quadratica di attraversare la soglia oltre la quale l'aggiunta di un lato può aumentare la signature. Il criterio di rango uno e la soglia hanno antecedenti diretti; la domanda nuova è se una famiglia chiusa di limiti di risposta sopravviva a operazioni naturali sui grafi. Dimostrano che la condizione è preservata dalla quadri-suddivisione di un lato arbitrario e dall'attaccamento di un modulo C4-C5 radicato in un vertice arbitrario. Partendo da C5, queste operazioni generano una classe infinita di grafi cactus planari connessi che raggiungono 2 sig(L(G)) = c(G) + 1. Ogni estensione di un lato soddisfa lo stesso limite, e un passo generale di rango uno dà un corollario a due lati. Le dimostrazioni combinano complementi di Schur con controlli locali esatti finiti e completi. La condizione di risposta è sufficiente, non nota come necessaria, e il limite ciclomatico universale resta aperto.