Authors: Gerard Jennhwa Chang ^1,2,3,4,5,6; Paul Dorbec ⁷; Hye Kyung Kim ⁸; André Raspaud ⁹; Haichao Wang ¹⁰; Weiliang Zhao ¹¹

• 1 Department of Mathematics [Taiwan]
• 2 Taida Institute for Mathematical Sciences [Taipei]
• 3 National Center for Theoretical Sciences [Taiwan]
• 4 Department of Mathematics [National Taiwan University]
• 5 Taida Institute for Mathematical Sciences [National Taiwan University]
• 6 National Center for Theoretical Sciences [National Taiwan University]
• 7 Combinatoire et Algorithmique
• 8 Department of Mathematics Education [Daegu]
• 9 Laboratoire Bordelais de Recherche en Informatique [LaBRI]
• 10 Department of Mathematics [Shanghai]
• 11 Zhejiang Industry Polytechnic College [Shaoxing]

Graph Theory

[en]
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.