debugMinor
Size of maximum clique given a fixed amount of edges?
Viewed 0 times
maximumedgesamountsizecliquefixedgiven
Problem
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.
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.
Solution
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.
$$\frac{1}{2} (\sqrt{8m + 1} + 1),$$
where $m = |E|$, provided of course that $|V|$ is large enough.
Context
StackExchange Computer Science Q#11360, answer score: 3
Revisions (0)
No revisions yet.