Distance eigenvalues just below −2 in cographs

A cograph has no induced path on four vertices. In a connected cograph, the distance matrix records the shortest path length between each pair of vertices. Is there a fixed interval immediately below −2 that contains no distance eigenvalue of any connected cograph?

Why it matters and what counts as progress

Why it matters: Connected cographs already have a gap just above −2. The question asks whether the spectrum can approach −2 from below.

What counts as progress: A uniform gap needs a proof for all connected cographs. A counterexample needs a family with a distance eigenvalue strictly below −2 that approaches −2.

How the problem developed

  1. 4 Nov 2026 · Problem statement [4]

    Pallabi Manna, Santanu Mandal and Fernando C. Tura Asked whether connected cographs share a gap immediately below −2 in their distance spectra.

  2. 10 Nov 2026 · Counterexample family [1][3]

    Horace Dong with Claude agents Reported a family of connected cographs with distance eigenvalues approaching −2 from below.

AI contribution

Connected cographs with distance eigenvalues just below −2

Horace Dong

For each positive integer m, joining a new universal vertex to the disjoint union of one isolated vertex and m edges gives a connected cograph. It has a distance eigenvalue strictly between −2−1/(2m)-2-1/(2m) and −2-2, so there is no uniform gap immediately below −2.

AI involvementAI-led
ImportanceModest
Technical verificationFormal (Lean)
Human understandingFew
Paper date:

Sources

  1. Horace Dong’s cograph note
  2. Release provenance for Paper 11
  3. Lean package and verification notes
  4. Manna, Mandal and Tura, Open Problem 14.2
  5. Conde, Dratman and Grippo’s earlier graph family
Publication history