A greedy partition lemma for directed domination

Abstract: A directed dominating set in a directed graph

D

is a set

S

of vertices of

V

such that every vertex

u i n V (D) s e t m i n u s S

has an adjacent vertex

v

in

S

with

v

directed to

u

. The directed domination number of

D

, denoted by

g a m m a (D)

, is the minimum cardinality of a directed dominating set in

D

. The directed domination number of a graph

G

, denoted

G a m m a_{d} (G)

, which is the maximum directed domination number

g a m m a (D)

over all orientations

D

of

G

. The directed domination number of a complete graph was first studied by Erd"{o}s [Math. Gaz. 47 (1963), 220--222], albeit in disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if

a l p h a

denotes the independence number of a graph

G

, we show that

a l p h a l e G a m m a_{d} (G) l e a l p h a (1 + 2 l n (n / a l p h a))

.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: A greedy partition lemma for directed domination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q665996)