What is the size of the smallest Maximal Independent Set (MIS) of a chain of nine nodes? A. 5 B. 4 C. 3 D. 2

GATE 2008 · Discrete Mathematics · Graph Connectivity · medium

Answer: 3

1. Apply the independent domination number formula: For P_9: i(P_9) = ceil(9/3) = ceil(3) = 3. The minimum MIS size is 3.
2. Verify construction {3, 6, 9} is a valid MIS: Independence: |6-3|=3>1, |9-6|=3>1, |9-3|=6>1; no two selected vertices share an edge. Maximality: non-members and their neighbors in the set: 1-adj-2-adj-3(in set); 4-adj-3(in set); 5-adj-6(in set); 7-adj-6(in set); 8-adj-9(in set). All non-members are dominated. MIS size = 3.