Upper bounds on the k-tuple domination number and k-tuple total domination number of a graph

Nader Jafari Rad

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=105951
Date :  2019/01/06
Publish in :    Australasian Journal of Combinatorics

Link :  https://ajc.maths.uq.edu.au/?page=get_volumes&volume=73
Keywords :bounds, k-tuple function, k-tuple, graph

Abstract :

---

Given a positive integer k, a subset S of vertices of a graph G is called a k-tuple dominating set in G if for every vertex v ∈ V (G), Nv ∩ S ≥ k. The minimum cardinality of a k-tuple dominating set in G is the k-tuple domination number γ×k(G) of G. A subset S of vertices of a graph G is called a k-tuple total dominating set in G if for every vertex v ∈ V (G), N(v) ∩ S ≥ k. The minimum cardinality of a k-tuple total dominating set in G is the k-tuple total domination number γ×k,t(G) of G. We present probabilistic upper bounds for the k-tuple domination number of a graph as well as for the k-tuple total domination number of a graph, and improve previous bounds given in J. Harant and M.A. Henning, Discuss. Math. Graph Theory 25 (2005), 29–34, E.J. Cockayne and A.G. Thomason, J. Combin. Math. Combin. Comput. 64 (2008), 251–254, and M.A. Henning and A.P. Kazemi, Discrete Appl. Math. 158 (2010), 1006–1011 for graphs with sufficiently large minimum degree under certain assumptions.