給定圖G，G的獨立集是彼此不相鄰的點所形成的集合。如果有一個G的獨 立集，並非G的任何其他獨立集的子集，我們則稱它為最大獨立集。最大獨立 集是在G中，具有最多點數的獨立集合。我們用α(G)表示G的最大獨立集的獨立 數。在G的子集中，如果存在一個子集S ⊆ V (G)，其所有點皆為每一個不在S中 的點的鄰居，我們則稱S為控制集。G的獨立控制集是G的控制集，同時也為G的 獨立集。當G的控制集中，最小的控制集的點數我們用 γ(G)來表示為控制數。 而最小的獨立控制集的點數我們則稱為獨立控制數，以i(G)表示。對於圖G，以 SID(G)表示獨立控制集的大小(即 SID(G) = {|D| : D是G的獨立控制集))， 且令 S(G)表示集合 {k : i(G) ≤ k ≤ α(G)}。如果 SID(G) = S(G),，則稱為 ID-perfect;另外如果S(G) − SID(G) = {α(G) − 1}，我們則稱為接近 ID-perfect。
本文研究了控製圖集的頻譜。我們證明了當 G為無爪圖，或者 G = H ×Pn,， 其中H = P2, P3, 或 Km，或者 G = T2,h，(T2,h 是具有h層的完整二元樹，且h為 奇數)，則 G是 ID-perfect的。我們還證明了，如果G = T2,h，且h是偶數， 則G為接近 ID-perfect。

Given a graph G, an independent set of G is a set of pairwise nonadjacent vertices of G. An independent set of G is a maximal independent set of G if it is not a subset of any other independent set of G. A maximum independent set of G is an independent set of G with the largest cardinality. The size of a maximum independent set of G is called the independence number of G and is denoted by α(G). In a graph G, a subset S ⊆ V (G) is a dominating set if every vertex not in S has a neighbor in S. An independent dominating set of G is a dominating set of G which is also an independent set of G. The domination number γ(G) is the minimum size of a dominating set of G. And the independent domination number of G, denoted by i(G), is the minimum size of an independent dominating set of G. For a graph G, let SID(G) denote the set of the sizes of the independent dominating sets of G(that is, SID(G) = {|D| : D is an independent dominating set of G}), andletS(G)denotetheset{k:i(G)≤k≤α(G)}. AgraphGissaid to be ID-perfect if SID(G) = S(G), and is said to be near ID-perfect if S(G) − SID(G) = {α(G) − 1}. We study the spectra of the independent dominating sets of graphs in this thesis. We prove that G is ID-perfect if G isclaw-free,orG=H×Pn,whereH=P2,P3,orKm,orG=T2,h (T2,h is the full binary tree of height h) with h is odd. We also prove that G is near ID-perfect if G = T2,h and h is even.

1 　 Introduction 　　 1
2 　 Preliminary 　　 2
3 　 Claw-free graphs 　　 2
4 　 Cartesian product of paths and cycles 　　 4
5 　 Full binary tree 　　 7

[1] S. Crevals, P. R.J. O ̈sterg ̊ard, Independent domination of grids, Discrete Math., 338 (2015) 1379–1384.
[2] W. Goddard, M. A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math., 313 (2013) 839-854.
[3] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[4] T. W. Haynes, S. T. Hedetniemi, P. J. Slater (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
[5] E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Generating all max- imal independent sets-NP-hardness and polynomial-time algorithms, SIAM J. Comput., 9 (1980) 558-565.
[6] J. Y. -T. Leung, Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs, J. Algorithms, 5 (1984) 22-35.
[7] G. J. Minty, On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory Ser. B, 28 (1980) 284-304.
[8] M. D. Plummer, Some covering concepts in graphs, J. Combin. Theory, 8 (1970), pp. 91-98.
[9] M.D. Plummer, Well-covered graphs: a survey, Quaest. Math., 16 (1993), pp. 253-287.
[10] G. Ravindra, Well-covered graphs, J. Combin. Inf. Syst. Sci., 2 (1977), pp. 20-21
[11] S. Tsukiyama, M. Ide, H. Ariyoshi, and I. Shirakawa, A new algorithm for generating all the maximal independent sets, SIAM J. Comput., 6 (1977) 505- 517.
[12] C. W. Yu and G. H. Chen, Generate all maximal independent sets in permu- tation graphs, Intern. J. Computer Math., 47 (1993) 1-8.