Elphick–Linz–Wocjan square-sum generalization of the Bollobás–Nikiforov conjecture

From papers

Let GG be a simple graph on nn vertices with adjacency matrix A(G)A(G), eigenvalues λ1λ2λn\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_n, clique number ω(G)\omega(G), and n+n^+ positive eigenvalues. Define

sk(G)=i=1kλi2,Λk(G)=sk(G)m,s_k(G)=\sum_{i=1}^k\lambda_i^2,\qquad \Lambda_k(G)=\frac{s_k(G)}{m},

where mm is the number of edges. Set

=min{n+,ω(G)}.\ell=\min\{n^+,\omega(G)\}.

Elphick–Linz–Wocjan conjecture. For every graph GG,

Λ(G)2(11ω(G)).\Lambda_\ell(G)\leq 2\left(1-\frac{1}{\omega(G)}\right).

This generalizes the Bollobás–Nikiforov conjecture and was proposed after computational investigation. The paper verifies it for graphs with at most O(m1.5ε)O(m^{1.5-\varepsilon}) triangles for some ε>0\varepsilon>0, including planar, book-free, and cycle-free graphs; the general statement remains open.

Progress summary

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

Sources & referencesView supporting material

Primary source

Hitesh Kumar and Shivaramakrishna Pragada, “Bollobás-Nikiforov Conjecture for graphs with not so many triangles”, arXiv:2407.19341 (2024).

Solutions 0

No solutions have been posted yet.