[Solved]: On the minimum order of a maximal independent set in cycle graphs and path graphs

Problem Detail: 

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.

Asked By : Mihai Bişog

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18535

 Ask a Question

 Download Related Notes/Documents