Given an integer , deciding whether a graph has a clique of size 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: , where is the largest eigenvalue of the adjacency matrix , is the number of vertices in , and is the clique number of . Strengthening this bound, Elphick and Wocjan proposed a conjecture in 2018, which is stated as follows: , where and are the eigenvalues of . In this paper, we have settled this conjecture for some classes of graphs, such as conference graphs, strongly regular graphs with (i.e., ) and , the line graph of , the Cartesian product of strongly regular graphs, and Ramanujan graph with .

生成讲解博客的中文版本

生成AI智能校验的中文版本