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 $\gamma _r^t(G)$, is the smallest cardinality of a total restrained dominating set of $G$. First, some exact values and sharp bounds for $\gamma _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 $\gamma _r^t(G)$ is NP-complete even for bipartite and chordal graphs in Section 4.
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 $\gamma _r^t(G)$, is the smallest cardinality of a total restrained dominating set of $G$. First, some exact values and sharp bounds for $\gamma _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 $\gamma _r^t(G)$ is NP-complete even for bipartite and chordal graphs in Section 4.
Ma, De-xiang; Chen, Xue-Gang; Sun, Liang. On total restrained domination in graphs. Czechoslovak Mathematical Journal, Tome 55 (2005) no. 1, pp. 165-173. http://geodesic.mathdoc.fr/item/CMJ_2005_55_1_a11/
@article{CMJ_2005_55_1_a11,
author = {Ma, De-xiang and Chen, Xue-Gang and Sun, Liang},
title = {On total restrained domination in graphs},
journal = {Czechoslovak Mathematical Journal},
pages = {165--173},
year = {2005},
volume = {55},
number = {1},
mrnumber = {2121664},
zbl = {1081.05086},
language = {en},
url = {http://geodesic.mathdoc.fr/item/CMJ_2005_55_1_a11/}
}
TY - JOUR
AU - Ma, De-xiang
AU - Chen, Xue-Gang
AU - Sun, Liang
TI - On total restrained domination in graphs
JO - Czechoslovak Mathematical Journal
PY - 2005
SP - 165
EP - 173
VL - 55
IS - 1
UR - http://geodesic.mathdoc.fr/item/CMJ_2005_55_1_a11/
LA - en
ID - CMJ_2005_55_1_a11
ER -
%0 Journal Article
%A Ma, De-xiang
%A Chen, Xue-Gang
%A Sun, Liang
%T On total restrained domination in graphs
%J Czechoslovak Mathematical Journal
%D 2005
%P 165-173
%V 55
%N 1
%U http://geodesic.mathdoc.fr/item/CMJ_2005_55_1_a11/
%G en
%F CMJ_2005_55_1_a11
[1] G. S. Domke, J. H. Hattingh et al: Restrained domination in graphs. Discrete Math. 203 (1999), 61–69. | DOI | MR
[2] M. A. Henning: Graphs with large restrained domination number. Discrete Math. 197/198 (1999), 415–429. | MR | Zbl
[3] E. A. Nordhaus and J. W. Gaddum: On complementary graphs. Amer. Math. Monthly 63 (1956), 175–177. | DOI | MR
[4] F. Jaeger and C. Payan: Relations du type Nordhaus-Gaddum pour le nombre d’absorption d’un granhe simple. C. R. Acad. Sci. Ser. A 274 (1972), 728–730. | MR
[5] M. R. Garey and D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979. | MR
