Score: 0

Strengthening Wilf's lower bound on clique number

Published: April 7, 2025 | arXiv ID: 2504.04836v1

By: Hareshkumar Jadav , Sreekara Madyastha , Rahul Raut and more

Potential Business Impact:

Finds hidden groups in networks faster.

Business Areas:
Quantum Computing Science and Engineering

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$.

Page Count
8 pages

Category
Computer Science:
Discrete Mathematics