Upper k-tuple domination in graphs
Gerard Jennhwa Chang, Paul Dorbec, Hye Kyung Kim, André Raspaud, Haichao Wang, Weiliang Zhao
Abstract
For a positive integer k, a k-tuple
dominating set of a graph G is a subset S of
V(G) such that |N[v] ∩S| ≥k for every
vertex v, where N[v] = {v}
∪{u ∈V(G):uv ∈ E(G)}. The
upper k-tuple domination number of G,
denoted by Γ×k(G), is the maximum
cardinality of a minimal k-tuple dominating set of
G. In this paper we present an upper bound on
Γ×k(G) for r-regular
graphs G with r ≥k, and characterize
extremal graphs achieving the upper bound. We also establish an upper
bound on Γ×2(G) for claw-free
r-regular graphs. For the algorithmic aspect, we show
that the upper k-tuple domination problem is NP-complete
for bipartite graphs and for chordal graphs.
Full Text: PDF PostScript