Aletheia Technologies
Search IT Let’s talk

PreprintGraph theory and discrete mathematicsPreprint; not peer reviewed

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

Zenodo deposit
Version
1.3

Abstract

This preprint studies the signature of the adjacency matrix of line graphs using the shifted signless Laplacian Q(G) − 2I, rooted-response methods, and reductions to the 2-core. It proves an exact pendant-forest reduction, a parity property for rooted-tree responses, a singular attachment lemma in the graph-port setting, and a rank-one criterion determining when a pendant leaf increases the line-graph signature. It establishes the universal upper bound s(L(G)) ≤ c(G): together with the constructive lower bound this gives ⌊(c + 1) / 2⌋ ≤ f(c) ≤ c, so f(c) is finite and its maximum is attained for every cyclomatic number c. The sharper inequality 2s(L(G)) ≤ c(G) + 1 remains a conjecture. The load-bearing mathematical certificates and principal computational results were independently checked.

Key formulae

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

Document status

The manuscript is a non-peer-reviewed preprint. No journal acceptance or publication is claimed.

Main contributions

  • An exact way to remove the tree-like parts hanging off a graph, and a formalism for how the rest of the graph responds to what is attached to it.
  • An upper bound that holds for every graph, and the bounds that follow for the largest value reachable at a fixed number of independent cycles.
  • Explicit counterexamples to the idea that the problem can always be reduced to the cyclic core of the graph, and constructions that reach the maximum for every number of independent cycles.

Stated limitations

  • The tighter inequality remains a conjecture: it is not proved here.
  • The exhaustive check in exact arithmetic was redone for every graph up to seven vertices. For eight vertices the result comes from an earlier computation, kept with the work. For nine vertices only a numerical check was run, which indicates but does not prove.
  • Version 1.2 corrects how graphs were written in the graph6 text format inside the second reproducibility package. The computations done on edge lists were unaffected and stand.

Versions and provenance

Related work

Verifiable provenance

The authoritative manuscript and reproducibility package are preserved on Zenodo. No separate public source-code repository is associated with this record.

Public materials

Technical details
Authoritative archive
Zenodo
Date of this file
This file has existed since at least 30 July 2026. The proof sits in a public register we do not control, and anyone can check it.
SHA-256
7c8afba6cc3be742d46675d51b5f167a55b66fc721901129c30a508d58a0e304
SHA-256 · Zenodo reproducibility package
739519f4f18ee84b97c89f1a23dc9512a05dea1687c8aa9a4e1eaff00795213e
Timestamp receipt (.ots)
Timestamp receipt (.ots)
Bitcoin blocks
960376, 960379, 960404, 960419
Verification record
AVR-AT-SP-2026-002-v1.3
Where to find this work elsewhere

Citation

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  -

Keywords