论文标题
改善了高管独立统治数的上限
Improved Upper Bound on Independent Domination Number for Hypercubes
论文作者
论文摘要
我们重新审查了确定超级管中独立支配数的问题，而在一般维度中，已知的上限仍然不紧密。我们在这里提出了一种建设性的方法，可以为$ n $ dimensional HyperCube $ q_n $构建独立的统治套件$ s_n $，其中$ n = 2p+1 $，$ p $是正整数$ \ ge 1 $，提供了一个独立的统治套件$ s_p $ $ p $ p $ p $ dimemensional hypercube $ q_p $ q_p $，已知。该过程还计算所有$ n = 2^k-1 $，$ k> 1 $的最小独立统治集。最后，我们确定独立支配数$α_n\ leq 3 \ times 2^{n-k-2} $对于$ 7 \ times 2^{k-2} {k-2} -1 \ leq n <2^{k+1} -1 $，$ k> 1 $。与较早的工作相比，这是该范围的改进的上限。
We revisit the problem of determining the independent domination number in hypercubes for which the known upper bound is still not tight for general dimensions. We present here a constructive method to build an independent dominating set $S_n$ for the $n$-dimensional hypercube $Q_n$, where $n=2p+1$, $p$ being a positive integer $\ge 1$, provided an independent dominating set $S_p$ for the $p$-dimensional hypercube $Q_p$, is known. The procedure also computes the minimum independent dominating set for all $n=2^k-1$, $k>1$. Finally, we establish that the independent domination number $α_n\leq 3 \times 2^{n-k-2}$ for $7\times 2^{k-2}-1\leq n<2^{k+1}-1$, $k>1$. This is an improved upper bound for this range as compared to earlier work.
