What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent.
(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 .