2017/09/05 by Sharareh Alipour, Alipour, Sharareh, Amir Jafari +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1709.01245
openalex publication_date 2017/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a connected graph of order n, whose minimum vertex degree is at least k. A subset S of vertices in G is a k-tuple total dominating set if every vertex of G is adjacent to at least k vertices in S. The minimum cardinality of a k-tuple total dominating set of G is the k-tuple total domination number of G, denoted by γ× k,t(G). Henning and Yeo in \citehen proved that if G is a cubic graph different from the Heawood graph, γ× 2, t(G) ≤ (5)/(6)n, and this bound is sharp. Similarly, a k-tuple dominating set is a subset S of vertices of G, V (G) such that |N[v] ∩ S| ≥ k for every vertex v, where N[v] = \v\∪ \u ∈ V(G) : uv ∈ E(G)\. The k-tuple domination number of G, denoted by γ× k(G), is the minimum cardinality of a k-tuple dominating set of G. In this paper, we give a simple approach to compute an upper bound for (r-1)-tuple total domination number of r-regular graphs. Also, we give an upper bound for the r-tuple dominating number of r-regular graphs. In addition, our method gives algorithms to compute dominating sets with the given bounds, while the previous methods are existential.