Pith. sign in

REVIEW 1 cited by

Strengthening Wilf's lower bound on clique number

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2504.04836 v1 pith:AJ7JKGK5 submitted 2025-04-07 cs.DM math.CO

classification cs.DMmath.CO
keywords lambdagraphscliquenumberboundgraphomegawilf
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

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

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A positive square-energy strengthening of Tur\'an's theorem

    math.CO 2026-07 conditional novelty 8.0 of 10

    Every n-vertex graph with clique number ω has √s⁺(G) ≤ (1−1/ω)n, where s⁺(G) is the sum of squared positive adjacency eigenvalues.

Pith tools