Abstract:

Suppose

D= (V, A) be a digraph. A subset S of V

is called a dominating set of D if for every vertex v in V – S, there exists a vertex u in S such

that (u, v)?A.We

use the notation

(D) to

represent the domination number of ? digraph, i.?., the minimum cardinality of

? set S ?V(D) which is dominating.In

this paper we present results concerning domination in digraphs along with

application in game theory. In terms of applications, the questions of Facility Location, Assignment Problems etc.

are very much related to the idea, of domination or independent domination on

digraph.

Keywords: Digraphs

1. Introduction

Domination and other related concepts in undirected

graphs are well studied. The pioneering work in digraphs in this area can be

ascribed to Berge, ??????, Konig, Grundy and Richardson, amongst others. This

paper detailing the results on digraphs has been naturally influenced by the

book ????? and JJypergraphs by Berge .In this paper some results on

domination in digraphs; the concept and results concerning solutions in ?

digraph and the application of some of these ideas to game theory. The

significant works in these areas by Blidia, Duchet, Galeana-Sanchez, Kwasnik,

Meyneil,Neumann-Lara,Roth, Smith, ???? and others are recorded in this

endeavor. We begin this journey with definitions of the major concepts.

2. Definitions

Perhaps

no other area of domination has as great ? need to standardize defini-tions and notation as that of

directed domination. Different terms are chosen for the same concept and the

same term is occasionally chosen for different con-cepts. We have tried to clarify the situation by giving

common alternate terms and pointing out differences in definitions. For this paper,

unless otherwise mentioned, ? graph D = (V, ?) consists of ? finite vertex set

V and an ??? set ? ??, where P is the set of all ordered pairs of distinct vertices of V.

That is, D has no multiple

loops and no multiple arcs (but pairs of opposite arcs are allowed). For this paper

we assume that the underlying graph of the digraph D is connected. In the terminology of Berge we are considering

connected 1-graphs without loops. Let D

= (V, ?) be such ? digraph. If ? = P then the digraph is complete.

Following Berge, ? subset S ?

V is absorbant if for every

vertex ? ? S there is ? vertex y

S

such that y is ? successor of x. We define ? set S ? V of ? digraph D to be ? dominating.

3.

Domination in Digraphs

Although the concept of

domination in graphs has received extensive attention as evidenced by this

volume, the same concept has been somewhat sparsely studied for digraphs. Even

bounds undirected graphs have not been considered and compared with their counterparts

for digraphs. In terms of applications, the questions of Facility Location, Assignment Problems etc.

are very much related to the idea, of domination or independent domination on

digraph. There have been over the year’s ? few papers on the domination number

of digraphs. These and other related concepts are presented below. We use the

notation

(D) to

represent the domination number of ? digraph, i.?., the minimum cardinality of

? set S ?V(D) which is dominating

4. New results

In

this section we explore some domination related results on digraphs analogous

to those of undirected graphs. First we look at some common b?unds for ?(D).

One of the earliest b?unds for the domination number for

any undirected graph

was proposed by Ore.

Theorem

4.1(Ore

85) For any graph G without isolates, ?(G) ?

,

where

n is the number of vertices.

This result does not hold for directed

graphs; ? counter example is the digraph K1,n,

n ? 2, with its arcs directed from the end vertices towards the central

vertex. The general bound which holds for digraphs is not very good for ?

majority of digraphs. We assume our digraphs to be those whose underlying

graphs are connected.

Observation

4.2 For any digraph’

with n vertices, ?(D) ? n -1.

This

bound is sharp because the domination number of the digraph ?1,n for

n ? 2 with its arcs directed

from the endvertices towards the central vertex is

n. Since very few graphs agree

with this bound we find other bounds which are

tighter for ? significant number of digraphs.

Theorem4.3

For any digraph D on n vertices,

?

?(D) ? n –

(D),

wh???

(D) denotes the maximum outdegree.

Proof. For

the upper bound we form ? dominating set of D by including the vertex ? of

maximum outdegree and all the other vertices in the digraph which are not

dominated by v. This set is clearly ? dominating set and has cardinality n –

(D).