Studies On Three Kinds Of Dominating Parameters Of Graphs

This thesis mainly studies three kinds of dominating parameters of graphs: the lower perfect neighborhood number of graphs, the refrained domination number of graphs and the ct-domination number of graphs, and discusses them with three respective chapters.On the lower perfect neighborhood number of graphs, this thesis gives the sufficient and necessary conditions of 9(G) = (G), and discusses the upper bound of the lower perfect neighborhood number of some special graphs. Especially, this thesis discusses it on tree in details and gives the tight upper bound (T) [n/3] by using the method of dividing the vertexes of tree into levels. These are the main results below:Theorem 2.4: In graph G, (G) = (G) if and only if (G) = i(G). Theorem 2.11: If T is a tree with n vertices, n 3, then (T) [n/3].On the refrained domination number of graphs, this thesis mainly discusses the bound of it by edge number. These are the main results below: Proposition 3.1: In the connected graph G which has n vertices, m edges and no isolates, r(G) 2(n - m), and the bound is attained if and only if G = P4. Proposition 3.2: In the graph G with n vertices, if the maximum degree is A, thenProposition 3.4: In the graph G with n vertices, if the minimum degree 2,Theorem 3.6: If G = (V, E] is a simple connected graph with n vertices and m edges, m n, which doesn't contain J1, J2,J3 as subgraphs, and the minimum degree 2, then r(G) (m+4)/3.Finally on the -domination number of graphs, this thesis mainly studies the relationship between ir (G) and ir(G), and gives the Nordhaus-Gaddum-type bound of (G) + (G), which solves two open problems of [7]. Additionally, it also discusses the graphs in which (G) + 1- (G) doesn't vary with . To some extent, it solves the second open problem of [7]. These are the main resultsbelow:Theorem 4.13: For any maximal a-irredundant set Ia of graph G = (V,E),there exists a maximal irredundant set of G of cardinality no more than |I |.Corollary 4.14: If G = (V, E), then ir(G) ir (G).Theorem 4.15: If G and G have no isolates, then when 0 < 1/2, we have (G) + (G) n; and when 1/2 < 1, we have (G) + (G) 2n - 4.