1
$\begingroup$

What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?


AFAIK :

In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent.

1--2--3--4--5--6--7--8--9 

(2,5,8) is the maximal independent set for a chain of 9 nodes. If we add any other node to the set then it will not be MIS.

IMO : Covering number should be "a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set." i.e. (2,4,6,8)

Can you explain "the independence number alpha(G) of a graph G and vertex cover number are related by

$\alpha(G)+\tau(G)=|G|$, where $n=|G|$ is the vertex count (West 2000). Consider my given problem please .

$\endgroup$
2
$\begingroup$

While (2,5,8) is an inclusionwise maximal independent set, it is not a maximum cardinality independent set. The graph parameter $\alpha(G)$ should be understood to mean the latter.

In the example you give, (1,3,5,7,9) is another maximal independent set, and this one has greater cardinality. The existence of this set shows that we have $\alpha(G) \geq 5$. It is not so hard to prove that no $6$-element set in $G$ is independent, so that we have $\alpha(G) = 5$.

$\endgroup$
  • $\begingroup$ Thanks for nice explanation. $\endgroup$ – 1 0 Nov 24 '15 at 14:58

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.