(Total) domination in prisms

Abstract: With the aid of hypergraph transversals it is proved that

g a m m a_{t} (Q_{n + 1}) = 2 g a m m a (Q_{n})

, where

g a m m a_{t} (G)

and

g a m m a (G)

denote the total domination number and the domination number of

G

, respectively, and

Q_{n}

is the

n

-dimensional hypercube. More generally, it is shown that if

G

is a bipartite graph, then

g a m m a_{t} (G s q u a r e K_{2}) = 2 g a m m a (G)

. Further, we show that the bipartite condition is essential by constructing, for any

k g e 1

, a (non-bipartite) graph

G

such that

g a m m a_{t} (G s q u a r e K_{2}) = 2 g a m m a (G) - k

. Along the way several domination-type identities for hypercubes are also obtained.

Full work available at URL: https://arxiv.org/abs/1606.08143

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

Cited In (12)

This page was built for publication: (Total) domination in prisms