Line-graph inertia of roses and generalized theta graphs

Abstract

Per un grafo G l'inerzia di adiacenza del line graph L(G) è determinata da quanti autovalori del Laplaciano senza segno Q(G) stanno sopra, su e sotto 2. Il manoscritto calcola in modo esatto l'inerzia di Q(G) − 2I, e quindi quella della matrice di adiacenza di L(G), compreso ogni caso singolare, per i grafi rosa e i grafi theta generalizzati. Entrambi i calcoli seguono da una riduzione comune: cancellando i vertici comuni restano cammini disgiunti, e l'eliminazione immagine-nucleo lascia le direzioni singolari del nucleo più uno scalare residuo per un grafo rosa, o una matrice 2 per 2 per un theta generalizzato. Le formule risultanti dipendono solo dalle lunghezze dei cammini modulo 4. Ne seguono il limite m_Q(G,2) ≤ c(G) per i theta generalizzati con almeno tre cammini e un confronto esatto con il limite congetturato 2s(L(G)) ≤ c(G) + 1, il cui margine cresce linearmente col numero ciclomatico su entrambe le classi, con uguaglianza solo per i cicli di lunghezza congrua a 1 modulo 4. La congettura generale non è dimostrata. Il lavoro dà anche un'estensione parziale ai cactus senza ponti; calcoli finiti esatti controllano ogni ramo delle formule.