I can see from this question that a $K_{r + 1}$-free graph with $n$ vertices and $e$ edges contains an independent set of order at least $$\frac{n}{2e/n + 1} \tag{1} $$ Since for a $C_{n}$/$P_{n}$ we know how many edges it contains it is easy to determine (1).

However, are there any particularities of cycle graphs and path graphs that would allow me, for such a graph $G$, to determine exactly $\min\{\mathopen|A\mathclose| : A\text{ is a maximal independent set of } G\}$, i.e. the minimum number of vertices that a maximal independent set of $G$ must contain.


The smallest maximal independent set in a cycle or path of length $n$ clearly has size about $n/3$. This can be seen by inspection and certainly doesn't need anything like Turán's theorem.

  • $\begingroup$ I think I'm missing something..how exactly can you see by inspection that a cycle or path of length $n$ clearly has the smallest maximal independent of size (I assume) $\lceil n/3 \rceil$? $\endgroup$ – Mihai Bişog Dec 2 '13 at 22:40
  • 1
    $\begingroup$ Consider a cycle of length $3\ell$. If you put every third vertex in the IS, the IS is clearly maximal; if you put fewer than that in, you'll have a pair of vertices in the IS with at least three consecutive non-IS vertices between them. At least one of those three could be adde to the IS so it's not maximal. Some small adjustment will deal with paths and the case where the cycle's length isn't an exact multiple of 3. $\endgroup$ – David Richerby Dec 2 '13 at 23:02

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.