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|Amathclose| : Atext{ 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
