On total restrained domination in graphs

Ma, De-xiang, Chen, Xue-Gang, and Sun, Liang. "On total restrained domination in graphs." Czechoslovak Mathematical Journal 55.1 (2005): 165-173. <http://eudml.org/doc/30935>.

@article{Ma2005,
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 $\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.},
author = {Ma, De-xiang, Chen, Xue-Gang, Sun, Liang},
journal = {Czechoslovak Mathematical Journal},
keywords = {total restrained domination number; Nordhaus-Gaddum-type results; NP-complete; level decomposition; total restrained domination number; Nordhaus-Gaddum-type results; NP-complete; level decomposition},
language = {eng},
number = {1},
pages = {165-173},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On total restrained domination in graphs},
url = {http://eudml.org/doc/30935},
volume = {55},
year = {2005},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 55
IS - 1
SP - 165
EP - 173
AB - 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.
LA - eng
KW - total restrained domination number; Nordhaus-Gaddum-type results; NP-complete; level decomposition; total restrained domination number; Nordhaus-Gaddum-type results; NP-complete; level decomposition
UR - http://eudml.org/doc/30935
ER -