Minimum number of edges required to limit the size of the independent set

Consider the following problem:

For $$k \le n$$, what is the smallest number of edges in the graph with $$n$$ vertices so that the maximum independent set has size at most $$k$$?

I.e., given an empty graph on $$n$$ vertices, I want to add the smallest number of edges so that the maximum independent set has size $$k$$. Let's denote it as $$A(n,k)$$. For example, $$A(8,3)=7$$, with edges $$1-2-3-1$$, $$4-5-6-4$$ and $$7-8$$ (two triangles and an edge).

I know that $$A(n,k) \le T(n-1, k)$$ where $$T$$ is https://oeis.org/A134546. In particular, I know that $$A(n,n) = 0$$ and $$A(n + 1,k) \le A(n, k) + \lfloor n / k \rfloor$$.

The particular construction is to maintain $$k$$ cliques so that the independent set can pick only vertex per clique. For example, for $$A(8,3)$$, the solution $$1-2-3-1$$, $$4-5-6-4$$ and $$7-8$$ consists of three cliques $$(1,2,3)$$, $$(4,5,6)$$, and $$(7,8)$$. When we add another vertex, we have $$A(9,3) \le A(8,3) + 2$$, since we can add edges $$8-9$$ and $$7-9$$ to have cliques $$(1,2,3)$$, $$(4,5,6)$$, and $$(7,8,9)$$.

Q: How to prove that we have equality, i.e. $$A(n + 1,k) = A(n, k) + \lfloor n / k \rfloor$$? My experiments show that it indeed holds, and, intuitively, it should hold.

I suspect there is some relation to Clique Cover, but I couldn't find it.

• You might find Turan's theorem helpful: en.m.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem Dec 27, 2023 at 19:15
• @jschnei, Thanks, this does provide a very good bound, but, unfortunately, it doesn't show equality. E.g., assuming that what I want to prove is in fact correct, starting from $n \ge 12$, the Turan's theorem starts underestimating the number of edges. Dec 27, 2023 at 21:09
• I am confused, if I understand your question correctly Turan's theorem should provide a tight bound. Note that an independent set is just a clique in the complement graph, so your question is equivalent to asking "what is the largest number of edges a graph with n vertices can have so that the maximum clique has size at most k"? This is exactly answered by Turan's theorem. Dec 28, 2023 at 0:27
• For $n=12$ and $k=8$, the answer is $4$, while Turan predicts $\ge 3$. This is if I use the last expression from en.m.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem#Statement (see also link.springer.com/content/pdf/10.1007/978-3-662-57265-8_41.pdf), which gives ${12 \choose 2} - (1-\frac{1}{8}) \cdot \frac{12^2}{2} = 3$. Do you have something else in mind? Dec 28, 2023 at 4:05
• If you read carefully, you'll see that the formula you are using is only an asymptotic bound. The actual "tight" value is given by some $(k-1)$-partite graph. You can phrase this as finding k-1 positive integers x_1, x_2, ..., x_{k-1} that sum to n and that maximize the sum_{i < j} x_ix_j. It is not too hard to show that to do this you want to set each x_i to either floor(n/(k-1)) or ceil(n/(k-1)). Dec 28, 2023 at 17:51