Fajtlowicz's conjecture on average neighbour degree and distance spectra

Less than 1 year old · traced to

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)∑u∈N(v)d(u),δ∗(G)=min⁡v∈V(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.

References

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.