Chang, Gerard Jennhwa and Dorbec, Paul and Kim, Hye Kyung and Raspaud, André and Wang, Haichaoet al. - Upper k-tuple domination in graphs

dmtcs:593 - Discrete Mathematics & Theoretical Computer Science, December 12, 2012, Vol. 14 no. 2
Upper k-tuple domination in graphs

Authors: Chang, Gerard Jennhwa and Dorbec, Paul and Kim, Hye Kyung and Raspaud, André and Wang, Haichao and Zhao, Weiliang

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.


Source : oai:HAL:hal-00903694v1
Volume: Vol. 14 no. 2
Section: Graph Theory
Published on: December 12, 2012
Submitted on: February 22, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 83 times.
This article's PDF has been downloaded 42 times.