4
$\begingroup$

Given an undirected graph $G = (V,E)$, what is the clique number $\omega(G)$ given $|E|$, i.e., the size of the largest clique in a graph with $|E|$ edges.

I think this is doable after realizing that the number of edges in a clique is equal to the triangular number: $$|E(K_k)| = \frac{1}{2}k(k-1).$$

I am looking for a closed formula.

$\endgroup$
3
  • 4
    $\begingroup$ Do you mean the maximal possible clique? Or finding the maximal clique size in a specific graph? The maximal possible size will clearly be $\min\{|V|,t\}$, where ${t\choose 2}=k$. Finding the maximal clique is NP-complete. $\endgroup$
    – Shaull
    Apr 16 '13 at 19:22
  • $\begingroup$ I'm looking for the maximal possible Clique. What does t refer to in this case? $\endgroup$ Apr 17 '13 at 2:56
  • $\begingroup$ $t$ is the solution to the equation $t(t-1)/2=k$. Intuitively - $t$ is the number of vertices you need for a clique with $k$ edges. $\endgroup$
    – Shaull
    Apr 17 '13 at 5:11
3
$\begingroup$

The graph can have clique number 1 (if we allow the graph to be disconnected), or 2 (consider a long path). The graph can have a clique of size at most $$\frac{1}{2} (\sqrt{8m + 1} + 1),$$ where $m = |E|$, provided of course that $|V|$ is large enough.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.