3.4 Result

and Analysis

Now

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

3.41(Ore

) 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

3.42 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 end vertices 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.

Theorem3.43

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).

Note that any vertex in D can dominate at most 1 +

(D) vertices.

In ? minimum dominating set S of D there

are ?(D) vertices, so they can dominate at most ?(D)(1 +

(D)) vertices. Since S is dominating this

number has to be at least n. Thus

we get the lower bound.

??

get another bound we look for certain

characteristics in ? digraph.

Observation 3.44 For any digraph D on n vertices, which has ? hamiltonian

circuit, ?(D) ?

Proof.

Let

D contain ? hamiltonian circuit

?. ?? dominate the vertices of D

it suffices to dominate the cycle ?. We know that the domination number

of ?

circuit is bounded above by

and so the same holds for the

digraph D.

Theorem

3.45

For ? strongly connected digraph D on

n vertices, ?(D) ?

In

addition to ?(D) we introduce some domination related parameters in digraphs,

in particular, the irredundance

number, the u???r irredundance

number and the u???? domination

number, analogous to those for undirected graphs. Recall that ? set S ?V(D) of ? digraph D is

? dominating set if for all

v

S, vis ? successor of some vertex in S. ? dominating set S is

? minimal dominating set if for

every v

S,Ov-OS-v

If u

O? – OS – ? , then u will be called ? private outneighbor (??n) of ? with

respect to S. See 38 for another characterization of minimal dominating sets

in digraphs.

Let ?(D), the upper domination

??????, denote the maximum cardinality of ? minimal dominating set. As in the

undirected case, we define an irredundant

set S ?V(D) to be ? set such that every ?

S has ? private outneighbor. The irredundance number ir(D) and the ????? irredundance number IR(D) are,

respectively, the minimum and maximum cardinalities of ? maximal irredundant

set.

The notion of ?

solution also yields parameters which are new to the field of digraphs. Let

i(D) and

(D) denote respectively the minimum and maximumcardinalities

of an independent dominating set. It must be pointed out that not ?ll digraphs

have independent dominating sets. As these are special cases of solutions,

these exist in digraphs which admit at least one solution. It must be mentioned

here that due to the concepts defined above the following string of

inequalities hold for any digraph D with ? solution,

r(D) ? ?(D) ? i(D) ? ?(D) ? ?(D) ? IR(D).

Researchers

interested in domination theory for undirected graphs are quite familiar with the corresponding inequality

chain. This chain raises some interesting questions about the structural properties of

digraphs D (having ? solution),

for which

1.?(D) = i(D),

2. ir(D) = ?(D),

?.?(D) = ?(D) = IR(D), or

4. i(D) ? ?(D).

The

following theorem is an interesting result for transitive digraphs.

Theorem

3.46 In ? transitive digraph

D, we have ?(D) = i(D) =

?(D)= ?(D) = IR(D).

Proof. Note that if D is ? transitive digraph so is its

reversal D-1. It is

then known that ? solution exists in D.

Moreover, from Berge’s theorem, we see that in D, every minimal absorbant set is independent and the kernel is

unique. This implies that ?(D) = I(D)

= ?(D)= ?(D).

?? show ? (D) = IR(D), suppose that S is an irredundant set with ?S? = IR(D). We will call such ? set an IR-set. Amongst all IR-sets let S

contain the minimum number of arcs in it. If S has no arcs, then certainly S is

independent and ? (D) ? IR(D) implying

? (D) = IR(D). So suppose that

< S > contains an arc (?, ?). Since S is irredundant y must have ?

private outneighbor ?1

S. But D is ? transitive digraph, so (? ,?1) must be an arc,

contradicting that y1 is ? private neighbor of x. Hence S is

independent and the result follows.

3.5.

Applications

3.51. Game

Theory (Von Neumann,

Morgenstern )

Suppose

that ? players, denoted by (1),(2),…,(n) can discuss together to

select ? point x from ? set ? (the “situations”). If

player (i) prefers situation ? to situation b, we shall write ? ?I

b. The individual preferences might not be compatible, and consequently it is

necessary to introduce the concept of effective preference. The

situation ? is said to be effectively preferred to b, or ? >

b, if there is ? set of players who prefer ? to b and who are ?ll

together capable of enforcing their preference for ?. However, effective

preference is not transitive; i.?., ?> b and b > ? does not

necessarily imply that ? > ?.

Consider the digraph D = (V, ?) where O(x)

denotes the set of situations effectively preferred to x. Let S be ? kernel of D.

Von Neumann and Morgen-stern suggested that the selection be confined to

the elements of S. Since S is independent, n? situation in S is effectively

preferred to any other situation in S. Since S is absorbant, for every

situation x

there is ? situation in S that is effectively

preferred to x, so that x can be immediately discarded.

3.52. Problem

in Logic (Berge,

Rao 06)

Let

us consider ? set of properties P = {?1,p2} and ?

set of theorems of the type: “property ?i implies property ?j’

. These theorems can be represented by ? directed graph D = (V, ?) with vertex

set P, where (?i, ?j) is an ??? if and only if it

follows from one or more of the existing theorems that ?i implies ?j

Suppose we want to show that n? arc of the complementary graph

is good to represent ? true

implication of that kind: more precisely, with each ??? (?, q) with ? ? q and

we assign ? student who has to find

an example where ? is fulfilled but not q (i.?., ? counter-example to the

statement that p implies q).

In

10 they determined the minimum number of students needed to show that ?ll the

possible (pairwise) implications are already represented in the di-graph D. It

was found that this number corresponded to the cardinality of the unique kernel

of the transitive digraph under study.

3.5

3 Facility Location

Let D = (V, ?) be ? digraph where the

vertices represent “locations” and there is an ??? from location ?

to location ? if location ? can be “reached?’ from

location ?. Assume that each “location” has ? weight

associated with it which represents some parameter pertinent to the study.

Choose ? subset of “locations” such that

those outside the set have an ??? incident from ? member of the set, which

means that ?ll the “locations” can be “serviced’ by the members

of the set S. Let w(S) denote the sum of the weights of the members of S. The

problem of finding such ? set S such that w(S) is minimized. The relevant graph

theoretic concept is that of directed domination.

3.6.

Conclusions and

Open Problems

Domination and other related topics in undirected

graphs are extensively stud-ied,

both theoretically and algorithmically. However, the corresponding topics on

digraphs have not received much attention, even though digraphs come up ??r?

naturally in modelling real world problems. With this view in mind, we have

made an attempt to survey some of the existing results on domination related

concepts on digraphs. We have also introduced some parameters on di-graphs analogous to domination

parameters on undirected graphs. As ? matter of fact, it seems that almost all

domination related problems on undirected graphs, if they make sense in

digraphs, may be investigated. Algorithmic aspects of these problems on

digraphs will be another good area, of research.