# Domination graph. Given a graph G, and a

Domination
is one of the important and rapidly growing areas of research in graph

theory.
A set D ? V is called a dominating set of
G = (V,E) if |NGv ? D| ? 1

for
all v ? V . The Minimum Domination problem
is to find a dominating set of

minimum
cardinality of the input graph. Given a graph G,
and a positive integer k,

the
Domination Decision problem is to determine whether G has a dominating

set
of cardinality at most k.
The domination number of a graph G, denoted as ?(G),

is
the minimum cardinality of a dominating set of G.

Though
the Minimum Domination problem is known to be NP-hard for
general

graphs
and remains NP-hard even for bipartite graphs, this problem admits polynomial
time algorithms for various special graph classes. In this thesis, we propose polynomial
time algorithms to compute a minimum dominating set of circular convex bipartite
graphs and triad-convex bipartite graphs. It is also known that for a bipartite
graph G, the Minimum
Domination problem cannot be approximated within (1??) ln n for
any ? > 0 unless NP ? DTIME(nO(log log n)). We strengthen the above result by proving that
even for star-convex bipartite graphs, the Minimum

Domination
problem cannot be approximated within (1??) ln n for
any ? > 0 unless

NP
? DTIME(nO(log log n)). We also prove that for bounded degree
star-convex

bipartite
graphs, the Minimum Domination problem is
linear-time solvable.

We
also study the algorithmic aspects of five variations of dominating set, namely

v

vi
Abstract

(i) Open neighborhood locating-dominating set, (ii) Outer-connected dominating

set,
(iii) Total outer-connected
dominating set, (iv) Disjunctive
Dominating set,

and
(v) Dominator coloring.

Let
G = (V,E) be a graph and let D be a subset of V .
Then (a) D is called

an
open neighborhood locating-dominating set (OLD-set) of
G if (i) NG(v)
? D ?=
?

for
all v ? V , and (ii)
NG(u) ? D ?= NG(v) ? D for every pair of distinct vertices

u, v ? V , (b) D is
called an outer-connected dominating set of
G if |NGv ? D| ? 1

for
all v ? V , and GV D
is connected, (c) D is called a total
outer-connected

dominating
set of G,
if |NG(v)?D| ? 1 for all v ? V , and GV D
is connected, (d)

D is called a disjunctive dominating set of
G if for every vertex v ? V D,
either v

is
adjacent to a vertex of D or
v has at least two
vertices in D at distance 2 from it.

In
this thesis, we strengthen the existing literature by proving that the above

four
variations of domination remains NP-hard for various important subclasses of

graphs.
We propose some polynomial time algorithms to solve these problems for

certain
graph classes. We propose approximation algorithms for these problems for

general
graphs and also prove some approximation hardness results.

A
dominator coloring of a graph G is a proper coloring of the vertices of G

such
that every vertex dominates all the vertices of at least one color class. The

minimum
number of colors required for a proper (dominator) coloring of G is called

the
chromatic number (dominator chromatic
number) of G and
is denoted by ?(G)

(?d(G)).

In
this thesis, we show that every proper interval graph G satisfies ?(G)+?(G)?

2
? ?d(G) ? ?(G)+?(G),
and these bounds are sharp. For a block graph G,
where

one
of the end block is of maximum size, we show that ?(G)+?(G)?1
? ?d(G) ?

?(G)+?(G).
We also characterize the block graphs with an end block of maximum

size
and attaining the lower bound.