Directed domination in oriented graphs

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. We extend this notion to directed domination of all graphs. If

a l p h a

denotes the independence number of a graph

G

, we show that if

G

is a bipartite graph, we show that

G a m m a_{d} (G) = a l p h a

. We present several lower and upper bounds on the directed domination number.

Recommendations

Cites work

Cited in

(23)

This page was built for publication: Directed domination in oriented graphs

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