Algorithmic Aspects Of K-domination In Trees And 2-domination In Block Graphs

Within the last more than thirty years, concurrent with the growth of computer science, graph theory has seen explosive growth. Perhaps the fastest growing area within graph theory is the study of domination in graphs. The rapid growth of domination research is attributable mainly to its so many applications to real world problems, such as coding theory, computer science, communication networks, monitor system and social network theory.For a fixed positive integer k,a k-domination set of a graph is a subset of V satisfying such condition:shortly speaking, G = (V, E) is a subset D of V such that every vertex in V - D is dominated by at least k vertices of D. The k-domination number r_k(G) is the minimum cardinality of a k-domination set of G. To establish an efficient algorithm for the k-domination in graphs, we use the notion of k-mix domination. Suppose G = (V,E) is a graph in which every vertex v is associated with a label M(v) = (t(v),k(v)), where t(v) G {B,R}, and k(v) is a nonnegative integer no larger than k. An k-mix domination set of G = (V,E) is a subset of D of V satisfying the following two conditions.(MD1) if t(v) = R, then v∈D(MD2) |N_G(v)∩D|≥k(v) for v∈G-DThe k-mix domination number r_kM(G) is the minimum cardinality of an k-mix domination set in G. Note that k-mix domination is k-domination with M(v) = (B, k) for all vertices v in V. The study of algorithms and complexity is meaningful and active in the study of the domination problems and its variants, one of which is to find the efficient algorithms on special classes of graphs. Trees and block graphs are well-known class of graphs, which forms a subclass of chordal graphs and strongly chordal graphs. They are very useful for modeling real world problems. Since trees and block graphs have good structure property, then many domination and related problems, which are NP-complete on arbitrary graphs, are polynomial solvable when restricted to trees and block graphs.In this thesis, we study the algorithms of two kinds of new domination-related parameters (k-domination and k-mix domination)in special graphs, and the following are our main results:(1) We present a linear time algorithm to compute a minimum cardinality k-mix dominating set in trees and prove its correctness. This algorithm could also be applied to compute a minimum cardinality k-dominating set in trees.(2) We also present a linear time algorithm to compute a minimum cardinality k-mix dominating set in block graph when k(v)≤2 and prove its correctness. This algorithm could also be applied to compute a minimum cardinality 2-dominating set in trees.(3) We prove that the k-domination problem is N P-complete for split graphs and for bipartite graphs.