Geodesic
On total restrained domination in graphs
Czechoslovak Mathematical Journal, Tome 55 (2005) no. 1, pp. 165-173
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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},
     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
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/

[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