超立方体网络的(d,k)控制数

(d,k)-Dominating Numbers of Hypercube Networks

(d,k)控制数是刻画容错网络中资源共亨可靠性的一个新参数.本文考虑了k维超立方体Qk的(d,k)控制数,得到:γ1,k(Qk)=2k-1(k>1);d=[k/2]+1(k>2)时,γd,k(Qk)=2;d≤[k/2](k≥4)时,3≤γd,k(Qk)≤2k-d+1;以及若d为正整数,且[k/d]=[k/(d-1)]+1,则γd,k(Qk)=γd,k(Qk),其中[k/d].d+1≤k1≤k.

The （d,k）-dominating number is a new measure to characterize reliability of resoures-shring in fault tolerant networks. This paper considers the （d,k）-dominating number of the k-dimensional hypercube net-work and obtains γ1,k（Qk）=2^k-1（k〉1）for d=[k/2]＋1（k〉2）,γd,k（Qk）=2 for d≤[k/2]（k≥4）and γd,k1（Qk）=γd,k（Qk）,for given values d if [k/d]=[k/d-1]＋1,where[k/d]·d＋1≤k1≤k.