Conjectured equality of spectral and positive-eigenvalue Nordhaus–Gaddum maxima

Let GG range over graphs on nn vertices, let G\overline G be its complement, let μ(G)\mu(G) be the spectral radius, and let s+(G)s^+(G) be the sum of the squares of the positive adjacency eigenvalues. Let f(n)f(n) be the piecewise function defined by

f(n)=0f(n)=0

for n2(mod3)n\equiv2\pmod3,

f(n)=(3n2)2+8(3n2)6f(n)=\frac{\sqrt{(3n-2)^2+8}-(3n-2)}6

for n1(mod3)n\equiv1\pmod3, and

f(n)=(3n1)2+8(3n1)6f(n)=\frac{\sqrt{(3n-1)^2+8}-(3n-1)}6

for n0(mod3)n\equiv0\pmod3. Square-root positive-eigenvalue conjecture.

maxv(G)=n(μ(G)+μ(G))=maxv(G)=n(s+(G)+s+(G))=4n353+f(n).\max_{v(G)=n}\bigl(\mu(G)+\mu(\overline G)\bigr)=\max_{v(G)=n}\bigl(\sqrt{s^+(G)}+\sqrt{s^+(\overline G)}\bigr)=\frac{4n}{3}-\frac53+f(n).

The authors report testing this conjecture on named graphs with up to 40 vertices without finding a counterexample; it remains open in the paper.

Sources & referencesView supporting material

Primary source

Clive Elphick and Mustapha Aouchiche, “Nordhaus-Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph”, arXiv:1607.08258 (2017).

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.