Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs |
| |
Authors: | Johannes H Hattingh Andrew R Plummer |
| |
Institution: | a Department of Mathematics and Statistics, University Plaza, Georgia State University, Atlanta, GA 30303, USA b Department of Mathematics, University of Johannesburg, P.O. Box 524, Auckland Park 2006, South Africa |
| |
Abstract: | Let G=(V,E) be a graph. A set S⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V-S is adjacent to a vertex in V-S. A set S⊆V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The total restrained domination number of G (restrained domination number of G, respectively), denoted by γtr(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?2 such that both G and are not isomorphic to P3, then . We also provide characterizations of the extremal graphs G of order n achieving these bounds. |
| |
Keywords: | Restrained Total Domination Nordhaus-Gaddum |
本文献已被 ScienceDirect 等数据库收录! |
|