| Title:
|
On total restrained domination in graphs (English) |
| Author:
|
Ma, De-xiang |
| Author:
|
Chen, Xue-Gang |
| Author:
|
Sun, Liang |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
55 |
| Issue:
|
1 |
| Year:
|
2005 |
| Pages:
|
165-173 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
total restrained domination number |
| Keyword:
|
Nordhaus-Gaddum-type results |
| Keyword:
|
NP-complete |
| Keyword:
|
level decomposition |
| MSC:
|
05C35 |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1081.05086 |
| idMR:
|
MR2121664 |
| . |
| Date available:
|
2009-09-24T11:21:53Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127967 |
| . |
| Reference:
|
[1] G. S. Domke, J. H. Hattingh et al: Restrained domination in graphs.Discrete Math. 203 (1999), 61–69. MR 1696234, 10.1016/S0012-365X(99)00016-3 |
| Reference:
|
[2] M. A. Henning: Graphs with large restrained domination number.Discrete Math. 197/198 (1999), 415–429. Zbl 0932.05070, MR 1674878 |
| Reference:
|
[3] E. A. Nordhaus and J. W. Gaddum: On complementary graphs.Amer. Math. Monthly 63 (1956), 175–177. MR 0078685, 10.2307/2306658 |
| Reference:
|
[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 0294161 |
| Reference:
|
[5] M. R. Garey and D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness.Freeman, New York, 1979. MR 0519066 |
| . |
