Research On Paired-domination Numbers And Rainbow Domination Numbers Of Graphs

Let G=(V,E) be a simple graph. For two subsets S,T (?) V(G), we say that S dominates T if every vertex in T\S is adjacent to some vertex in S. In particular, if S dominates V(G) then S is said to be a dominating set of G; that is, S (?) V(G) is a dominating set of G if every vertex of G not in S is adjacent to one in S. The domination number γ(G) is the size of the smallest dominating set of G. The domination problem concerns testing whether γ(G)≤ k for a given graph G and a value κ. It is a classical NP-complete decision problem in computational complexity theory and also a natural model of location problem in operations research. Based on the background of the various location problems, all kinds of domination problems are now widely studied and this subject is one of the hottest topics in graph theory. The dissertation concerns two domination problems:paired-domination problem and rainbow domination problem.Let G=(V, E) be a simple graph without isolated vertices. A set S C V is a paired-dominating set if every vertex in V\S has at least one neighbor in S and G[S], the subgraph induced by S, contains a perfect matching. The paired-domination number of G, denoted by γpr(G), is the minimum cardinality of a paired-dominating set of G. A conjecture of Goddard and Henning (2009) says that if G (?) P is a connected graph of order n with minimum degree δ(G)≥ 3, then-γpr(G)≤ 4n/7, where P is the Petersen graph. We confirm this conjecture for κ-regular graphs with κ≥ 4 in Chapter 2. In Chapter 3, we show that the conjecture holds for graphs with minimum degree at least nine.An edge-coloring of a graph G=(V, E) is a map c:E â†' C, where C is the color set. Let (G, c) be an edge-colored graph with an edge-coloring c of graph G. A rainbow subgraph is a subgraph whose edges have distinct colors. A set of disjoint rainbow stars S is a rainbow dominating star set of (G, c) if S cover V(G). The rainbow domination number of (G, c), denoted by γ(G), is the minimum cardinality of a rainbow dominating star set. In Chapter 4, a polynomial-time algorithm is proposed for finding a minimum rainbow dominating star set and hence the valueγ(T) for an edge-colored tree (T, c).