Aletheia Technologies
Cerca EN Parliamone

PreprintTeoria dei grafi e matematica discretaPreprint; non sottoposto a peer review

Line-Graph Signature Beyond the 2-Core: Exact Counterexamples, Rooted Response, and Extremal Constructions at Fixed Cyclomatic Number

Deposito Zenodo
Versione
1.3

Abstract

Questo preprint studia la segnatura della matrice di adiacenza dei line graph tramite la matrice laplaciana senza segno traslata Q(G) − 2I, metodi di risposta radicata e riduzioni al 2-core. Il manoscritto dimostra una riduzione esatta delle foreste pendenti, una proprietà di parità per le risposte degli alberi radicati, un lemma di attacco singolare nel modello con porta sul grafo e un criterio di rango uno che determina quando una foglia pendente aumenta la segnatura del line graph. Stabilisce il limite superiore universale s(L(G)) ≤ c(G): insieme al limite inferiore costruttivo si ottiene ⌊(c + 1) / 2⌋ ≤ f(c) ≤ c, quindi f(c) è finita e il suo massimo è raggiunto per ogni numero ciclomatico c. La disuguaglianza più fine 2s(L(G)) ≤ c(G) + 1 resta una congettura. I certificati matematici portanti e i principali risultati computazionali sono stati controllati in modo indipendente.

Formule chiave

Q(G)−2IQ(G)-2I
s(L(G))≤c(G)s(L(G))\le c(G)
⌊(c+1)/2⌋≤f(c)≤c\lfloor(c+1)/2\rfloor\le f(c)\le c

Stato del documento

Il manoscritto è un preprint non sottoposto a peer review. Non viene dichiarata alcuna accettazione o pubblicazione da parte di una rivista.

Contributi principali

  • Un modo esatto di eliminare le parti ad albero che pendono da un grafo, e un formalismo per descrivere come il resto del grafo risponde a ciò che vi si attacca.
  • Un limite superiore valido per ogni grafo, e i limiti che ne discendono per il massimo raggiungibile a parità di numero di cicli indipendenti.
  • Controesempi espliciti all'idea che si possa sempre ridurre il problema al nucleo ciclico del grafo, e costruzioni che raggiungono il massimo per ogni numero di cicli indipendenti.

Limiti dichiarati

  • La disuguaglianza più stretta resta una congettura: non è dimostrata qui.
  • La verifica esaustiva con calcolo esatto è stata rifatta per tutti i grafi fino a sette vertici. Per otto vertici il risultato viene da una campagna di calcolo precedente, conservata insieme al lavoro. Per nove vertici è stato fatto solo un controllo numerico, che indica ma non dimostra.
  • La versione 1.2 corregge come i grafi erano trascritti nel formato testuale graph6 dentro il secondo pacchetto di riproducibilità. I conti fatti sulle liste di archi non erano toccati dall'errore e restano validi.

Versioni e provenienza

Lavori collegati

Provenienza verificabile

Il manoscritto e il pacchetto di riproducibilità autoritativi sono conservati su Zenodo. A questo record non è associato un repository pubblico separato.

Materiali pubblici

Dettagli tecnici
Archivio autoritativo
Zenodo
Data del file
Questo file esiste almeno dal 30 luglio 2026. La prova sta in un registro pubblico che non controlliamo noi, e chiunque può controllarla.
SHA-256
7c8afba6cc3be742d46675d51b5f167a55b66fc721901129c30a508d58a0e304
SHA-256 · Zenodo reproducibility package
739519f4f18ee84b97c89f1a23dc9512a05dea1687c8aa9a4e1eaff00795213e
Ricevuta della data (.ots)
Ricevuta della data (.ots)
Blocchi Bitcoin
960376, 960379, 960404, 960419
Record di verifica
AVR-AT-SP-2026-002-v1.3
Dove trovare questo lavoro altrove

Citazione

BibTeX RIS
BibTeX 
@misc{Paone2026LineGraphSignature,
  author = {Paone, Andrea and Paone, Marco},
  title = {Line-Graph Signature Beyond the 2-Core: Exact Counterexamples, Rooted Response, and Extremal Constructions at Fixed Cyclomatic Number},
  month = jul,
  year = {2026},
  date = {2026-07-30},
  version = {1.3},
  doi = {10.5281/zenodo.21706797},
  url = {https://doi.org/10.5281/zenodo.21706797},
  note = {Preprint; not peer reviewed}
}
RIS 
TY  - UNPB
AU  - Paone, Andrea
AU  - Paone, Marco
TI  - Line-Graph Signature Beyond the 2-Core: Exact Counterexamples, Rooted Response, and Extremal Constructions at Fixed Cyclomatic Number
PY  - 2026
DA  - 2026-07-30
DB  - Zenodo
ET  - 1.3
DO  - 10.5281/zenodo.21706797
UR  - https://doi.org/10.5281/zenodo.21706797
N1  - Preprint; not peer reviewed
KW  - line graph
KW  - graph signature
KW  - graph inertia
KW  - spectral graph theory
KW  - signless Laplacian
KW  - cyclomatic number
KW  - 2-core
KW  - rooted response
KW  - Schur complement
KW  - pendant forest
KW  - extremal graph theory
KW  - exact computation
ER  -

Parole chiave