Strengthening Wilf's lower bound on clique number
By: Hareshkumar Jadav , Sreekara Madyastha , Rahul Raut and more
Potential Business Impact:
Finds hidden groups in networks faster.
Given an integer $k$, deciding whether a graph has a clique of size $k$ is an NP-complete problem. Wilf's inequality provides a spectral bound for the clique number of simple graphs. Wilf's inequality is stated as follows: $\frac{n}{n - \lambda_{1}} \leq \omega$, where $\lambda_1$ is the largest eigenvalue of the adjacency matrix $A(G)$, $n$ is the number of vertices in $G$, and $\omega$ is the clique number of $G$. Strengthening this bound, Elphick and Wocjan proposed a conjecture in 2018, which is stated as follows: $\frac{n}{n - \sqrt{s^{+}}} \leq \omega$, where $s^+ = \sum_{\lambda_{i} > 0} \lambda_{i}^2$ and $\lambda_i$ are the eigenvalues of $A(G)$. In this paper, we have settled this conjecture for some classes of graphs, such as conference graphs, strongly regular graphs with $\lambda = \mu$ (i.e., $srg(n, d, \mu, \mu)$) and $n\geq 2d$, the line graph of $K_{n}$, the Cartesian product of strongly regular graphs, and Ramanujan graph with $n\geq 11d$.
Similar Papers
On cuts of small chromatic number in sparse graphs
Combinatorics
Graphs can be split into smaller, easier parts.
Sublevels in arrangements and the spherical arc crossing number of complete graphs
Combinatorics
Finds the minimum number of crossings in a drawing.
The non-existence of some Moore polygons and spectral Moore bounds
Combinatorics
Finds biggest networks with strong connections.