June 10, 2023
Doost Ali Mojdeh

Doost Ali Mojdeh

Degree: Professor
Address: Department of Mathematics, University of Mazandaran, Babolsar, Iran
Education: Ph.D in Mathematics (Graph Theory and Combinatorics)
Phone: 011-35302448
Faculty: Faculty of Mathematical Sciences


Title Revisiting $k$-tuple Dominating Sets with Emphasis on Small Values of $k$
Type Article
Double domination number, Double Slater number, NP-complete, Tree, k-tuple domatic partition, Full graphs
Journal Bulletin of the Malaysian Mathematical Sciences Society
DOI https://doi.org/10.1007/s40840-022-01269-1
Researchers Babak Samadi (First researcher) , Nasrin Soltankhah (Second researcher) , Doost Ali Mojdeh (Third researcher)


For any graph G of order n with degree sequence d1 ≥ · · · ≥ dn, we define the double Slater number s×2(G) as the smallest integer t such that t + d1 + · · · + dt−e ≥ 2n − p in which e and p are the number of end-vertices and penultimate vertices of G, respectively. We show that γ×2(G) ≥ s×2(G), where γ×2(G) is the wellknown double domination number of a graph G with no isolated vertices. We prove that the problem of deciding whether the equality holds for a given graph is NPcomplete even when restricted to 4-partite graphs. We also prove that the problem of computing γ×2(G) is NP-hard even for comparability graphs of diameter two. Some results concerning these two parameters are given in this paper improving and generalizing some earlier results on double domination in graphs. We give an upper bound on the k-tuple domatic number of graphs with characterization of all graphs attaining the bound. Finally, we characterize the family of all full graphs, leading to a solution to an open problem given in a paper by Cockayne and Hedetniemi (Networks 7: 247–261, 1977).