is one of the important and rapidly growing areas of research in graph
A set D ? V is called a dominating set of
G = (V,E) if |NGv ? D| ? 1
all v ? V . The Minimum Domination problem
is to find a dominating set of
cardinality of the input graph. Given a graph G,
and a positive integer k,
Domination Decision problem is to determine whether G has a dominating
of cardinality at most k.
The domination number of a graph G, denoted as ?(G),
the minimum cardinality of a dominating set of G.
the Minimum Domination problem is known to be NP-hard for
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
problem cannot be approximated within (1??) ln n for
any ? > 0 unless
? DTIME(nO(log log n)). We also prove that for bounded degree
graphs, the Minimum Domination problem is
also study the algorithmic aspects of five variations of dominating set, namely
(i) Open neighborhood locating-dominating set, (ii) Outer-connected dominating
(iii) Total outer-connected
dominating set, (iv) Disjunctive
(v) Dominator coloring.
G = (V,E) be a graph and let D be a subset of V .
Then (a) D is called
open neighborhood locating-dominating set (OLD-set) of
G if (i) NG(v)
? D ?=
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
all v ? V , and GV D
is connected, (c) D is called a total
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,
adjacent to a vertex of D or
v has at least two
vertices in D at distance 2 from it.
this thesis, we strengthen the existing literature by proving that the above
variations of domination remains NP-hard for various important subclasses of
We propose some polynomial time algorithms to solve these problems for
graph classes. We propose approximation algorithms for these problems for
graphs and also prove some approximation hardness results.
dominator coloring of a graph G is a proper coloring of the vertices of G
that every vertex dominates all the vertices of at least one color class. The
number of colors required for a proper (dominator) coloring of G is called
chromatic number (dominator chromatic
number) of G and
is denoted by ?(G)
this thesis, we show that every proper interval graph G satisfies ?(G)+?(G)?
? ?d(G) ? ?(G)+?(G),
and these bounds are sharp. For a block graph G,
of the end block is of maximum size, we show that ?(G)+?(G)?1
? ?d(G) ?
We also characterize the block graphs with an end block of maximum
and attaining the lower bound.