For every graph, min{s+, s-} is at least 2m/chi_vec(G), resolving a conjecture of Wocjan, Elphick and Anekstein.
Bollob\'as-Nikiforov Conjecture for graphs with not so many triangles
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
Bollob\'as and Nikiforov conjectured that for any graph $G \neq K_n$ with $m$ edges \[ \lambda_1^2+\lambda_2^2\le \bigg( 1-\frac{1}{\omega(G)}\bigg)2m\] where $\lambda_1$ and $\lambda_2$ denote the two largest eigenvalues of the adjacency matrix $A(G)$, and $\omega$ denotes the clique number of $G$. This conjecture was recently verified for triangle-free graphs by Lin, Ning and Wu and for regular graphs by Zhang. Elphick, Wocjan and Linz proposed a generalization of this conjecture. In this note, we verify this generalized conjecture for the family of graphs on $m$ edges, which contain at most $O(m^{1.5-\varepsilon})$ triangles for some $\varepsilon > 0$. In particular, we show that the conjecture is true for planar graphs, book-free graphs and cycle-free graphs.
fields
math.CO 1years
2024 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Conic programming to understand sums of squares of eigenvalues of graphs
For every graph, min{s+, s-} is at least 2m/chi_vec(G), resolving a conjecture of Wocjan, Elphick and Anekstein.