On total restrained domination in graphs

De-xiang Ma; Xue-Gang Chen; Liang Sun

Czechoslovak Mathematical Journal (2005)

  • Volume: 55, Issue: 1, page 165-173
  • ISSN: 0011-4642

Abstract

top
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 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 γ r t ( G ) , is the smallest cardinality of a total restrained dominating set of G . First, some exact values and sharp bounds for γ 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 γ r t ( G ) is NP-complete even for bipartite and chordal graphs in Section 4.

How to cite

top

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 -

References

top
  1. 10.1016/S0012-365X(99)00016-3, Discrete Math. 203 (1999), 61–69. (1999) MR1696234DOI10.1016/S0012-365X(99)00016-3
  2. Graphs with large restrained domination number, Discrete Math. 197/198 (1999), 415–429. (1999) Zbl0932.05070MR1674878
  3. 10.2307/2306658, Amer. Math. Monthly 63 (1956), 175–177. (1956) MR0078685DOI10.2307/2306658
  4. Relations du type Nordhaus-Gaddum pour le nombre d’absorption d’un granhe simple, C. R. Acad. Sci. Ser.  A 274 (1972), 728–730. (1972) MR0294161
  5. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979. (1979) MR0519066

NotesEmbed ?

top

You must be logged in to post comments.