2
$\begingroup$

An independent set is a set of vertices in a graph, no two of which are adjacent. A maximal independent set is an independent set that you can not add any vertex. I want to know if the number of all maximal independent set is an exponential number.

$\endgroup$

1 Answer 1

4
$\begingroup$

Yes, consider the graph that consists of vertices $v_1,\ldots,v_{2n}$ and edges $(v_1,v_2),(v_3,v_4),\ldots,(v_{2n-1},v_{2n})$. This graph has exactly $2^n$ maximal independent sets, because for each $0\leq i\leq n-1$, we can either choose the vertex $v_{2i}$ or $v_{2i+1}$.

$\endgroup$
7
  • $\begingroup$ Please can give me a reference $\endgroup$
    – tounsy
    Dec 17, 2014 at 10:22
  • 1
    $\begingroup$ @A.Schulz No, that graph would only have 1 maximal independent set, since any independent set that does not contain all vertices can be extended by adding another vertex, so it is not maximal. $\endgroup$ Dec 17, 2014 at 10:22
  • $\begingroup$ But if you take the graph with no edges and n vertices we have one maximal independent set that is the set with all vertices ? $\endgroup$
    – tounsy
    Dec 17, 2014 at 10:25
  • 4
    $\begingroup$ @tounsy No, it does have $2^n$ maximal independent sets. The graph consists of $n$ components and each component is two vertices connected by a single edge. For each component of the graph, I can pick either endpoint of the edge to be in the independent set. $\endgroup$ Dec 17, 2014 at 10:30
  • 3
    $\begingroup$ @tounsy That bound would be obtained by using $n/3$ triangles in place of Tom's $n/2$ edges. Also, note that you are expected to do some research before asking questions here so you should probably have found the Moon-Moser bound when you did that. $\endgroup$ Dec 17, 2014 at 10:46

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.