Cartesian product graphs and k-tuple total domination

Abstract: A

k

-tuple total dominating set (

k

TDS) of a graph

G

is a set

S

of vertices in which every vertex in

G

is adjacent to at least

k

vertices in

S

; the minimum size of a

k

TDS is denoted

g a m m a_{i m e s k, t} (G)

. We give a Vizing-like inequality for Cartesian product graphs, namely

g a m m a_{i m e s k, t} (G) g a m m a_{i m e s k, t} (H) l e q 2 k g a m m a_{i m e s k, t} (G B o x H)

provided

g a m m a_{i m e s k, t} (G) l e q 2 k h o (G)

, where

h o

is the packing number. We also give bounds on

g a m m a_{i m e s k, t} (G B o x H)

in terms of (open) packing numbers, and consider the extremal case of

g a m m a_{i m e s k, t} (K_{n} B o x K_{m})

, i.e., the rook's graph, giving a constructive proof of a general formula for

g a m m a_{i m e s 2, t} (K_{n} B o x K_{m})

.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Cartesian product graphs and \(k\)-tuple total domination