Fajtlowicz's conjecture on average neighbour degree and distance spectra

Let GG be a finite simple connected graph of order n=V(G)2n=|V(G)|\ge2. For each vertex vv, let d(v)d(v) be its degree and N(v)N(v) its open neighbourhood, and define

d(v)=1d(v)uN(v)d(u),δ(G)=minvV(G)d(v).d^*(v)=\frac1{d(v)}\sum_{u\in N(v)}d(u),\qquad \delta^*(G)=\min_{v\in V(G)}d^*(v).

Let D(G)D(G) be the distance matrix of GG, and write λmin(D(G))\lambda_{\min}(D(G)) for its smallest eigenvalue. Fajtlowicz's conjecture. If GG has order at least three and girth at least five, then

δ(G)λmin(D(G)).\delta^*(G)\le-\lambda_{\min}(D(G)).

This is a Graffiti conjecture attributed to Fajtlowicz's 1998 Written on the Wall report and recorded by Aouchiche and Hansen. Its resolution is not established by the supplied text.

Sources & referencesView supporting material

Primary source

Samuil Petkov, “Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284”, arXiv:2607.27452 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.