On total restrained domination in graphs
Authors:
- 1 March 2005
- journal article
- Published by Institute of Mathematics, Czech Academy of Sciences in Czechoslovak Mathematical Journal
- Vol. 55 (1) , 165-173
Abstract
In this paper we initiate the study of total restrained domination in graphs. Let G = (V,E) be a graph. A total restrained dominating set is a set S \( \subseteq \) V where every vertex in V - S is adjacent to a vertex in S as well as to another vertex in V - S, and every vertex in S is adjacent to another vertex in S. The total restrained domination number of G, denoted by γ r t (G), is the smallest cardinality of a total restrained dominating set of G. First, some exact values and sharp bounds for γ r t (G) are given in Section 2. Then the Nordhaus-Gaddum-type results for total restrained domination number are established in Section 3. Finally, we show that the decision problem for γ r t (G) is NP-complete even for bipartite and chordal graphs in Section 4.
Keywords
This publication has 3 references indexed in Scilit:
- Restrained domination in graphsDiscrete Mathematics, 1999
- Graphs with large restrained domination numberDiscrete Mathematics, 1999
- On Complementary GraphsThe American Mathematical Monthly, 1956