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.

Improve this question
$\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$
    – robowolverine
    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.

Improve this answer
$\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.