Some comments on the Slater number

Abstract: Let

G

be a graph with degree sequence

d_{1} g e q l d o t s g e q d_{n}

. Slater proposed

s e l l (G) = m i n s : (d_{1} + 1) + c d o t s + (d_{s} + 1) g e q n

as a lower bound on the domination number

g a m m a (G)

of

G

. We show that deciding the equality of

g a m m a (G)

and

s e l l (G)

for a given graph

G

is NP-complete but that one can decide efficiently whether

g a m m a (G) > s e l l (G)

or

g a m m a (G) l e q l e f t (l e f t l c e i l l n l e f t (f r a c n (G) s e l l (G) i g h t) i g h t c e i l + 1 i g h t) s e l l (G)

. For real numbers

a l p h a

and

with

, let

be the class of non-null graphs

G

such that every non-null subgraph

H

of

G

has at most

many edges. Generalizing a result of Desormeaux, Haynes, and Henning, we show that

for every graph

G

in

with

a l p h a l e q f r a c 32

. Furthermore, we show that

g a m m a (G) / s e l l (G)

is bounded for graphs

G

in

if and only if

a l p h a < 2

. For an outerplanar graph

G

with

s e l l (G) g e q 2

, we show

g a m m a (G) l e q 6 s e l l (G) - 6

. In analogy to

s e l l (G)

, we propose

s e l l_{t} (G) = m i n s : d_{1} + c d o t s + d_{s} g e q n

as a lower bound on the total domination number. Strengthening results due to Raczek as well as Chellali and Haynes, we show that

s e l l_{t} (T) g e q f r a c n + 2 - n_{1} 2

for every tree

T

of order

n

at least

2

with

n_{1}

endvertices.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Some comments on the Slater number