Geodesic
On total restrained domination in graphs
Czechoslovak Mathematical Journal, Tome 55 (2005) no. 1, pp. 165-173

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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.
Classification : 05C35, 05C69
Keywords: total restrained domination number; Nordhaus-Gaddum-type results; NP-complete; level decomposition 
@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},
     publisher = {mathdoc},
     volume = {55},
     number = {1},
     year = {2005},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CMJ_2005__55_1_a11/
%G en
%F CMJ_2005__55_1_a11
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/