Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650730 | Discrete Mathematics | 2008 | 8 Pages |
Let G=(V,E)G=(V,E) be a graph. A set S⊆VS⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V-SV-S is adjacent to a vertex in V-SV-S. A set S⊆VS⊆V is a restrained dominating set if every vertex in V-SV-S is adjacent to a vertex in S and to a vertex in V-SV-S. The total restrained domination number of G (restrained domination number of G , respectively), denoted by γtr(G)γtr(G) (γr(G)γr(G), respectively), is the smallest cardinality of a total restrained dominating set (restrained dominating set, respectively) of G. We bound the sum of the total restrained domination numbers of a graph and its complement, and provide characterizations of the extremal graphs achieving these bounds. It is known (see [G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar, L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999) 61–69.]) that if G is a graph of order n⩾2n⩾2 such that both G and G¯ are not isomorphic to P3P3, then 4⩽γr(G)+γr(G¯)⩽n+2. We also provide characterizations of the extremal graphs G of order n achieving these bounds.