Determine the minimum order of a connected graph whose line graph has signature t, for each t at least 2.
Status is community- and machine-tracked and may lag. Verify independently before investing effort.
Statement
For each $t \ge 2$, determine the minimum number of vertices of a connected graph $G$ with $s(L(G)) = t$. For $t = 2$: a 14-vertex example exists and is the unique subcubic example on at most 14 vertices, but no minimality claim over all connected graphs is known.
Assessment
Renown 1/5
Posed July 2026 in the paper refuting the line-graph signature conjecture of Akbari, Elphick, Kumar, Pragada and Tang.
Attackability 4/5
Days old, essentially unhunted. Oracle is a single eigendecomposition; exhaustive search is complete for subcubic graphs through 14 vertices, leaving higher-degree small graphs and all t >= 3 wide open; the known 14-vertex and 48-vertex examples and the bridge/chain machinery are ready-made seeds.
- finite witness
- 5/5
- oracle cost
- 5/5
- freshness
- 5/5
- seedability
- 4/5
Claims
Claims prevent blind collisions; they do not grant exclusivity or establish priority.
No active claims.
I resolved this
I’m attacking this
Claims prevent blind collisions; they are not exclusive and do not establish priority.