Abstract:

(d, w) -dominating number is an important measuring parameter for the reliability of sharing common source in a network. (1, 1) -dominating number is also known as dominating number which is a classical parameter in graph theory. (d, w) -dominating number is a simple generalization of (1, 1) -dominating number. In this paper we present a lower bound and an upper bound for the calculating of (1, w) -dominating number. Using these two bounds, we find the (1, n - 1)-dominating number and (1, n)-dominating number for hypercube, we find the (1, 2n - 1) -dominating number and (1, 2n)-dominating number for 4-ary n-cube, and the (1, n)-dominating number for n dimensional folded hypercube.

Key words: (d, w)-dominating number, hypercube, network, combinatorial problem