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.