On total restrained domination in graphs |
| |
| Authors: | De-Xiang Ma Xue-Gang Chen Liang Sun |
| |
| Institution: | (1) The College of Information Science and Engineering, Shandong University of Science and Technology, 266510 Qingdao, P.R. China;(2) The College of Information Science and Engineering, Shandong University of Science and Technology, 266510 Qingdao, P.R. China;(3) Dept. of Applied Mathematics, Beijing Institute of Technology, 100081 Beijing, P.R. China |
| |
| 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
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.This work was supported by National Natural Sciences Foundation of China (19871036). |
| |
| Keywords: | total restrained domination number Nordhaus-Gaddum-type results NP-complete level decomposition |
| 本文献已被 SpringerLink 等数据库收录！ |
|
