Twin domination number of Tournaments

Abstract: Let

D = (V, A)

be a digraph. A subset

S

of

V

is called a twin dominating set of

D

if for every vertex

v i n V - S

, there exists vertices

u_{1}, u_{2} i n S

such that

(v, u_{1})

and

(u_{2}, v)

are arcs in

D

. The minimum cardinality of a twin dominating set in

D

is called the twin domination number of

D

and is denoted by

g a m m a^{*} (D)

. The upper orientable twin domination number of a graph

G

is

D O M^{*} (G) = m a x g a m m a^{*} (D) | D e x t i s a n o r i e n t a t i o n o f G .

It has been conjectured that for the complete graph

K_{n}

with

n g e q 8

,

D O M^{*} (K_{n}) = l e f t l c e i l f r a c n + 1 2 i g h t c e i l

. In this work we prove

D O M^{*} (K_{8}) = D O M^{*} (K_{9}) = 4

and establish new upper bounds for

D O M^{*} (K_{n})

, disproving the same above conjecture for all

n g e q 8

.

This page was built for publication: Twin domination number of Tournaments