Skip to main content
deleted 238 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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)$$\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. This is already addressed in the comments.

However, unlike Turan's theorem, it may be tricky to get a characterization of all the extremal graphs. For example, we cannot generate all of them simply by adding edges to $\overline{T(n,k)}$. To see this, consider $\overline{T(2k,k)}$. NoteEdit. Note that $\overline{T(2k,k)}$the bound is a perfect matching withtight for $k$ edges$n=2k$, soand all the graphs we getextremal examples do come from Turan's theorem are simply trees that have perfect matchings. But one can instead take any tree on $2k$ vertices with no independent set of size $k+1$. There are many such trees See Flo Pfender's answer, and mostwhich corrects an error in a previous version of them do not have perfect matchingsthis answer.

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)$ by Turan's theorem, and 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. This is already addressed in the comments.

However, unlike Turan's theorem, it may be tricky to get a characterization of all the extremal graphs. For example, we cannot generate all of them simply by adding edges to $\overline{T(n,k)}$. To see this, consider $\overline{T(2k,k)}$. Note that $\overline{T(2k,k)}$ is a perfect matching with $k$ edges, so the graphs we get from Turan's theorem are simply trees that have perfect matchings. But one can instead take any tree on $2k$ vertices with no independent set of size $k+1$. There are many such trees, and most of them do not have perfect matchings.

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.

fixed indexing for Turan's theorem
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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)$ by Turan's theorem, and 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. This is already addressed in the comments.

However, unlike Turan's theorem, it may be tricky to get a characterization of all the extremal graphs. For example, we cannot generate all of them simply by adding edges to $\overline{T(n,k)}$. To see this, consider $\tau(2k-2, k$)$\overline{T(2k,k)}$. Note that $\overline{T(2k-2,k)}$ $\overline{T(2k,k)}$ is a perfect matching with $k-1$$k$ edges, so the graphs we get from Turan's theorem are simply trees that have perfect matchings. But one can instead take any tree on $2k-2$$2k$ vertices whose maximumwith no independent set hasof size $k-1$$k+1$. There are many such trees, and most of them do not have perfect matchings.

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)$ by Turan's theorem, and 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. This is already addressed in the comments.

However, unlike Turan's theorem, it may be tricky to get a characterization of all the extremal graphs. For example, we cannot generate all of them simply by adding edges to $\overline{T(n,k)}$. To see this, consider $\tau(2k-2, k$). Note that $\overline{T(2k-2,k)}$ is a perfect matching with $k-1$ edges, so the graphs we get from Turan's theorem are simply trees that have perfect matchings. But one can instead take any tree on $2k-2$ vertices whose maximum independent set has size $k-1$. There are many such trees, and most of them do not have perfect matchings.

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)$ by Turan's theorem, and 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. This is already addressed in the comments.

However, unlike Turan's theorem, it may be tricky to get a characterization of all the extremal graphs. For example, we cannot generate all of them simply by adding edges to $\overline{T(n,k)}$. To see this, consider $\overline{T(2k,k)}$. Note that $\overline{T(2k,k)}$ is a perfect matching with $k$ edges, so the graphs we get from Turan's theorem are simply trees that have perfect matchings. But one can instead take any tree on $2k$ vertices with no independent set of size $k+1$. There are many such trees, and most of them do not have perfect matchings.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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)$ by Turan's theorem, and 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. This is already addressed in the comments.

However, unlike Turan's theorem, it may be tricky to get a characterization of all the extremal graphs. For example, we cannot generate all of them simply by adding edges to $\overline{T(n,k)}$. To see this, consider $\tau(2k-2, k$). Note that $\overline{T(2k-2,k)}$ is a perfect matching with $k-1$ edges, so the graphs we get from Turan's theorem are simply trees that have perfect matchings. But one can instead take any tree on $2k-2$ vertices whose maximum independent set has size $k-1$. There are many such trees, and most of them do not have perfect matchings.