0
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2013 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, 2013 at 23:02

Your Answer

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

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