3
$\begingroup$

Using a small modification to Turáns theorem we can find the minimum amount of edges a graph $G$ on $n$ vertices must have so it does not have an independent set of size $k$. Is there a similar result if we add the restriction that $G$ is a connected graph?

$\endgroup$
3
  • 2
    $\begingroup$ A rather good upper bound is the bound offered by Turans theorem plus $k-2$ $\endgroup$
    – Gorka
    Jun 6, 2014 at 4:43
  • $\begingroup$ that bound looks sharp, I'd be surprised if it wasn't (at least for n large). $\endgroup$ Jun 7, 2014 at 4:15
  • $\begingroup$ using the modification of Turan we see the optimal graph is made up of $k-1$ components, each of which is a clique. So we only need k-2 edges to connect those cliques. $\endgroup$
    – Gorka
    Jun 7, 2014 at 4:18

3 Answers 3

3
$\begingroup$

Just a partial answer, expanding Tony's:

The statement is true for $n=2k$ (i.e. you need exactly $(2k-1)$ edges to avoid an independent set of size $k+1$ in a connected graph), and the extremal graphs are exactly the trees with a perfect matching.

Proof: Clearly, you need $2k-1$ edges to make it connected. And $2k-1$ are sufficient, take any tree without an independence set of size $k+1$ (a path would do).

It remains the classification. Clearly we only need to consider trees.

If a tree on $2k$ vertices has no independent set of size $k+1$, then it has a perfect matching: proof by induction on $k$. $k=1$ is trivial. For $k>1$, consider a non-leaf $v$. If we delete $v$, the remaining forest has exactly one odd component $T_v$, all other components are even. Otherwise, pick the bigger part in the bipartition of each component, and you end up with an independent set of size $k+1$. By the same reason, each component of size $2k'$ has independence number $k'$, and thus by induction a perfect matching. It remains to consider $T_v+ v$. If this tree had an independent set of size larger then half, we could combine this with the parts in the other components not incident to $v$ to create an independence set of size $k+1$, again a contradiction. So, again by induction, $T_v+v$ has a perfect matching.

If a tree on $2k$ vertices has a perfect matching, then it has no independent set of size $k+1$: This follows trivially from PHP.

$\endgroup$
3
  • $\begingroup$ I'm sorry I'm not familiar with php, what is that? $\endgroup$
    – Gorka
    Jun 9, 2014 at 17:16
  • $\begingroup$ Nice. I'll update my answer. $\endgroup$
    – Tony Huynh
    Jun 9, 2014 at 17:19
  • 2
    $\begingroup$ PHP=pigeon hole principle. $\endgroup$ Jun 9, 2014 at 17:25
1
$\begingroup$

This is not an answer, but it became a bit too long for a comment.

If we let $\tau(n,k)$ be the number of edges in the complement of the Turan graph $T(n,k)$, then the minimum number of edges a connected graph with no independent set of size $k+1$ is probably $\tau(n,k)+k-1$. Note that it is at least $\tau(n,k)+1$ by Turan's theorem (it cannot be exactly $\tau(n,k)$ since $\overline{T(n,k)}$ is the unique graph on $n$ vertices with $\tau(n,k)$ edges and no independent set of size $k+1$). On the other hand, it is at most $\tau(n,k)+k-1$ since we can add $k-1$ edges to the complement of $T(n,k)$ to make it connected.

Edit. Note that the bound is tight for $n=2k$, and all the extremal examples do come from Turan's theorem. See Flo Pfender's answer, which corrects an error in a previous version of this answer.

$\endgroup$
3
  • $\begingroup$ we are adding k-2 right? because there are k-1 components, and we only need k-2 edges to connect them. $\endgroup$
    – Gorka
    Jun 9, 2014 at 16:14
  • $\begingroup$ I re-indexed so that I am excluding an independent set of size $k+1$. So for me, I add $k-1$ edges. $\endgroup$
    – Tony Huynh
    Jun 9, 2014 at 16:42
  • $\begingroup$ Oh, I see, then I agree. $\endgroup$
    – Gorka
    Jun 9, 2014 at 16:52
1
$\begingroup$

First, tthere are other extremal examples than the complement of the Turan graph for $n = 3k-4$. The $3k-4$ example is given by the following. There is also an easy construction that shows that the guess of Turan theorem plus $k-2$ is not enough for $n = 2k-1$.

example

Let $G$ be a $K_r$ free graph who has a connected complement. What is the maximal number of edges $G$ can have?

I will prove for $n \geq Cr^2$ for a small constant $C$ that the Turan graph minus $r-2$ edges is the best (and only) possible.

The key observation for the other statement is that if a graph is $K_r$ free and has close to the number of edges in the Turan graph, then the graph is close to an $r-1$ partite graph (and indeed if close is replaced by very close, one can replace it is a $r-1$ partite graph). At least two of the proofs of Turan's theorem in this paper generalize to prove such a statement (the second and third) for large graphs, though it is not obvious (especially how the second generalizes). Erdos-Simonivits is related, but the bound is too weak for your question. I will outline how to extend Erdos' proof which is unpublished work of Furedi, though can be found in a presentation of his here.

He shows the following in a very elegant manner.

Claim: Let $G$ be a graph such that (i) $G$ is $K_r$ free (ii) $e(G) \geq |T(n,r-1)| - t$ Then one can remove at most $t$ edges from $G$ to create a $r-1$ partite graph.

(Pf) Let $x_1 \in V(G)$ such that the degree of $x_1$ is chosen maximally. Let $V_1$ be all the non-neighbors of $G$. Similarly, let $x_2$ be chosen such that the degree of $x_2$ in the induced subgraph of $G \setminus V_1$ is maximal. Let $V_2$ be all of the vertices in $G \setminus V_1$ that are not adjacent to $x_2$. Repeat this process (chossing $x_j$ so that the degree in the induced subgraph $G \setminus (V_1 \cup \ldots \cup V_{j-1})$ is maximal) to eventually get vertices $x_1 , \ldots , x_{r-2}$ and vertex sets $V_1 , \ldots , V_{r-1}$. Note that since $G$ is $K_r$ free, $V_{r-1}$ is an independent set. Let $G_1$ be the spanning subgraph containing exactly the edges. Then $$e(G) \leq \sum_{i=1}^{r-2} d_{V_{i+1} \cup \ldots \cup V_{r-1}}(x_i) |V_i|.$$ But in this counting, we counted each edge inside $G_1$ twice. Thus $$e(G) \leq \sum_{i=1}^{r-2} d_{V_{i+1} \cup \ldots \cup V_{r-1}}(x_i) |V_i| - e(G_1) \leq T(n,r-1) - e(G_1),$$ and the result follows by the assumption.

This result quickly implies the following result.

Claim: Let $G$ be a graph such that (i) $G$ is $K_r$ free (ii) $e(G) \geq |T(n,r-1)| - (r-2)$ (iii) $G$ contains at least $Cr^2$ vertices for some computable (small) constant $C$ Then $G$ is a $r-1$ partite graph.

(Sketch of Proof, which can be found here) Let $G_0$ be the maximal spanning $r-1$ partite graph and $G_1 = (V(G) , E(G) \setminus E(G_0))$. By the previous claim $|E_(G_1)| \leq r-2$. If one of the color classes of $G_0$ is smaller than say $\frac{n}{2(r-1)}$, then this contradicts $(ii)$ and $(iii)$. If there is an edge in $G_1$, then using the fact that $G$ is $K_r$ free, one can show that, without much difficulty, that $|E(G_0)| \leq |T(n,r-1)| - \frac{n}{2(r-1)}$. This is a contradiction to $(ii)$ and $(iii)$.

This stability theorem immediately implies that the Turan graph minus $r-2$ edges is the best (and only) possible construction for a graph with maximum number of edges that is $K_r$ free and who has a connected complement.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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