  A set $D\subseteq V$ of a graph $G=(V,E)$ is called a restrained dominating
set of $G$ if every vertex not in $D$ is adjacent to a vertex in $D$ and to a
vertex in $V \setminus D$. The \textsc{Minimum Restrained Domination} problem
is to find a restrained dominating set of minimum cardinality. Given a graph
$G$, and a positive integer $k$, the \textsc{Restrained Domination Decision}
problem is to decide whether $G$ has a restrained dominating set of cardinality
a most $k$. The \textsc{Restrained Domination Decision} problem is known to be
NP-complete for chordal graphs. In this paper, we strengthen this
NP-completeness result by showing that the \textsc{Restrained Domination
Decision} problem remains NP-complete for doubly chordal graphs, a subclass of
chordal graphs. We also propose a polynomial time algorithm to solve the
\textsc{Minimum Restrained Domination} problem in block graphs, a subclass of
doubly chordal graphs. The \textsc{Restrained Domination Decision} problem is
also known to be NP-complete for split graphs. We propose a polynomial time
algorithm to compute a minimum restrained dominating set of threshold graphs, a
subclass of split graphs. In addition, we also propose polynomial time
algorithms to solve the \textsc{Minimum Restrained Domination} problem in
cographs and chain graphs. Finally, we give a new improved upper bound on the
restrained domination number, cardinality of a minimum restrained dominating
set in terms of number of vertices and minimum degree of graph. We also give a
randomized algorithm to find a restrained dominating set whose cardinality
satisfy our upper bound with a positive probability.
