EUVIMEDEUVIMED entdecken
Crossref

Strengthening Wilf's Lower Bound on Clique Number

Hareshkumar Jadav, Sreekara Madyastha, Rahul Raut, Ranveer Singh

ACM Communications in Computer Algebra · 01.12.2025 · 59 (4) · 129-133

DOI: 10.1145/3832046.3832060 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Communications in Computer Algebra, online erschienen am 18.08.2026. Verfasst von Hareshkumar Jadav und 3 weiteren Autor:innen. Die Arbeit nennt 8 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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: [EQUATION], where λ 1 is the largest eigenvalue of the adjacency matrix A(G), n is the number of vertices in G , and Ω is the clique number of G. Strengthening this bound, Elphick and Wocjan proposed a conjecture in 2018, which is stated as follows: [EQUATION], where [EQUATION] and λ 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 λ = μ (i.e., srg(n,d,μ,μ) ) and n ≥ 2 d , the line graph of K n , the Cartesian product of strongly regular graphs, and Ramanujan graph with n ≥ 11 d.

Zitieren

APA

Jadav, H., Madyastha, S., Raut, R., & Singh, R. (2025). Strengthening Wilf's Lower Bound on Clique Number. ACM Communications in Computer Algebra, 59(4), 129-133. https://doi.org/10.1145/3832046.3832060

Vancouver

Jadav H, Madyastha S, Raut R, Singh R. Strengthening Wilf's Lower Bound on Clique Number. ACM Communications in Computer Algebra. 2025;59(4):129-133. doi:10.1145/3832046.3832060

BibTeX
@article{Jadav2025,
  author = {Jadav, Hareshkumar and Madyastha, Sreekara and Raut, Rahul and Singh, Ranveer},
  title = {Strengthening Wilf's Lower Bound on Clique Number},
  journal = {ACM Communications in Computer Algebra},
  year = {2025},
  volume = {59},
  number = {4},
  pages = {129--133},
  doi = {10.1145/3832046.3832060}
}
Kostenlos starten →