On total restrained domination in graphs

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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$ \subseteq $$ \end{document}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 γrt(G), is the smallest cardinality of a total restrained dominating set of G. First, some exact values and sharp bounds for γrt(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 γrt(G) is NP-complete even for bipartite and chordal graphs in Section 4.