5
$\begingroup$

Given integers $k$ and $n$ with $2 \le k < n$, how does one construct a graph on $n$ vertices that contains no $k$-clique and has the maximal number of edges?

This sounds like basic combinatorics, but I don't know where to find the result. Pointers would be welcome if this is well-known.

Ideally I would like a deterministic procedure to construct such a maximal graph in $n^{O(1)}$ time.

One graph with $n$ vertices that is guaranteed not to contain $K_k$ is $\overline{K_{n-k+2} + \overline{K_{k-2}}}$, the complement of the graph formed by the disjoint union of $K_{n-k+2}$ and $k-2$ isolated vertices. Whenever one picks $k$ vertices from it, at least two of these must be from the subset which is completely disconnected, so they cannot form a clique. This can clearly be constructed in polynomial time, and is quite dense for $k$ close to $n$. However, this construction yields rather sparse graphs when $k$ is small relative to $n$, so it seems unlikely to be the optimal construction.

$\endgroup$
7
$\begingroup$

Turan's theorem exactly characterizes the densest graphs on n vertices with no k clique. The Turan graphs are the maximal graphs, and they're very easy to construct. Is this what you want?

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