If G = (V, E) is an undirected graph, a subset I of V is called independent if no two vertices in I are adjacent. An independent set I is called maximal if no vertex v can be added to I with I ˆª {v} independent. The independence number of G, denoted β(G), is the size of a largest independent set in G.
(a) For each graph in Fig. 11.85 find two maximal independent sets with different sizes.
(b) Find β(G) for each graph in part (a).
(c) Determine β(G) for each of the following graphs: (i) K1,3; (ii) k2,3; (iii) K3,2; (iv) K4,4; (v) K4,5; (vi) Km,n, m, n ˆˆ Z+.
(d) Let I be an independent set in G = (V, E). What type of subgraph does I induce in ?

Transcribed Image Text:

Figure 11.85