Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
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
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.
References:
[1] G. S. Domke, J. H. Hattingh et al: Restrained domination in graphs. Discrete Math. 203 (1999), 61–69. DOI 10.1016/S0012-365X(99)00016-3 | MR 1696234
[2] M. A. Henning: Graphs with large restrained domination number. Discrete Math. 197/198 (1999), 415–429. MR 1674878 | Zbl 0932.05070
[3] E. A. Nordhaus and J. W. Gaddum: On complementary graphs. Amer. Math. Monthly 63 (1956), 175–177. DOI 10.2307/2306658 | MR 0078685
[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
[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
Search
Partner of
