Nordhaus-Gaddum type inequalities for multiple domination and packing parameters in graphs

D. A. Mojdeh, Babak Samadi

Published 2016-10-20Version 1

We study the Nordhaus-Gaddum type results for $(k,k,j)$ and $k$-domination numbers of a graph $G$ and investigate these bounds for the $k$-limited packing and $k$-total limited packing numbers in graphs. As the special cases $(k,k,j)=(1,1,0)$ and $(k,k,j)=(1,2,0)$ we give upper bounds on the sum of total domination number and double domination number of a graph and its complements, respectively, stronger than those conjectured by Harary and Haynes (1996). Moreover, we establish upper bounds on the sum and product of packing and open packing numbers and characterize all graphs attaining these bounds.