Double domination in maximal outerplanar graphs

Abstract: In a graph

G

, a vertex dominates itself and its neighbors. A subset

S s u b s e t e q V (G)

is said to be a double dominating set of

G

if

S

dominates every vertex of

G

at least twice. The double domination number

g a m m a_{i m e s 2} (G)

is the minimum cardinality of a double dominating set of

G

. We show that if

G

is a maximal outerplanar graph on

n g e q 3

vertices, then

g a m m a_{i m e s 2} (G) l e q l f l o o r f r a c 2 n 3 f l o o r

. Further, if

n g e q 4

, then

g a m m a_{i m e s 2} (G) l e q m i n l f l o o r f r a c n + t 2 f l o o r, n - t

, where

t

is the number of vertices of degree

2

in

G

. These bounds are shown to be tight. In addition, we also study the case that

G

is a striped maximal outerplanar graph.

This page was built for publication: Double domination in maximal outerplanar graphs