平衡超立方体的控制数

摘  要： 控制数可用于衡量互连网络的可靠性，而平衡超立方体网络作为超立方体网络的变体，有许多优良的性质。因此，根据平衡超立方体的性质，确定了n=1，2，3时平衡超立方体的控制数以及符号控制数的具体值，提出了关于n维平衡超立方体控制数的一个问题。

关键词： 互连网络;平衡超立方体;控制数;符号控制数

中图分类号： TP393    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2020.09.044

本文著录格式：金永丽. 平衡超立方体的控制数[J]. 软件，2020，41（09）：165167+177

【Abstract】： The domination number can be used to measure the reliability of the interconnection network， and the balanced hypercube network， as a variant of the hypercube network， has many excellent properties. Therefore， According to the properties of balanced hypercubes， the specific values of domination numbers and signed domination numbers of balanced hypercubes when n=1，2，3 are determined， and a problem about domination numbers of n-dimensional balanced hypercubes is put forward.

【Key words】： Interconnection network; Balanced hypercube; Domination number; Signed domination number

0  引言

平衡超立方体（balanced hypercubes）是互连网络的拓扑结构，由Wang和Huang[3]提出，作为超立方体的变体，它有超立方体及其变体所没有的特性。例如，维平衡超立方体的直径不大于维超立方体的直径，并且每个处理器都有相同邻点的备份处理器。正因为有这样的特性，近年来引起了许多学者们的广泛关注。特别地，Yang[4]证明了平衡超立方体是偶泛连通的;Lü[5]等人得到了平衡超立方体的匹配排除数和条件匹配排除数;Lü和Wu[6]证明了平衡超立方体有两个边不交的哈密尔顿圈。关于其它互连网络拓扑结构性质的研究可参见文献[7-11]。

图的控制理论在图论本身的研究领域应用广泛，而图的控制数是控制理论中的一个基本参数，因此给出准确的控制数具有重要的意义。图的控制数问题是NPC问题，确定图的控制数是比较困难的，所以许多结构复杂的图的控制数仍待研究。其中，文献[12-16]对一些互连网络的控制数进行了研究。本文根据平衡超立方体的性质，给出了低维情形下的点控制数及符号控制数，提出了一个关于维平衡超立方体点控制数的问题。

本文的结构如下：第二部分给出了平衡超立方体、控制数、符号控制数的定义及本文用到的性质和引理;第三部分研究了平衡超立方体的点控制数;第四部分给出了时平衡超立方体的符号控制数。文中所提及的术语和符号参见文献[1-2]。

1  预备知识

下面我们介绍平衡超立方体的定义及其部分性质，控制数和符号控制数的定义及其相关引理。

分别如图1，图2，图3所示。

参考文献

[1]BONDY J A， MURTY U S R. Graph Theory with Applications[M]. Amsterdam： Elsevier， 1976.

[2]徐保根. 图的控制与染色理论[M]. 武汉： 华中科技大学出版社， 2013.

[3]WU Jie， HUANG Ke. The Balanced Hypercube： A Cube-Based System for Fault-Tolerant Applications[J]. IEEE Transactions on Computers， 1997， 46（4）： 484-490.

[4]YANG Ming-Chien. Bipanconnectivity of Balanced Hypercubes[J]. Computeres Mathematics with Applications， 2010， 60（7）： 1859-1867.

[5]LV Huazhong， LI Xianyue， ZHANG Heping. Matching Preclusion for Balanced Hypercubes[J]. Theoretical Computer Science， 2012， 465： 10-20.

[6]LV Huazhong， WU Tingzeng. Edge-Disjoint Hamiltonian Cycles of Balanced Hypercubes[J]. Information Processing Letters， 2019， 144： 25-30.

[7]張欣， 师海忠. 交叉立方体连通圈网络的Hamilton分解[J]. 软件， 2015， 36（8）： 92-98.

[8]王海锋， 师海忠. M?bius 超立方体网络的Hamilton分解[J].软件， 2015， 36（10）： 85-89.

[9]胡艳红， 师海忠. 关于冒泡排序连通圈网络猜想的一个注记[J]. 软件， 2016， 37（01）： 91-100.

[10]师海忠， 汪生龙. 关于煎饼网络及层次环煎饼网络的几个猜想[J]. 软件， 2018， 39（1）： 94-100.

[11]师海忠， 陈璐璐. k次Herschel—师连通圈网络[J]. 软件， 2018， 39（7）： 72-78.

[12]HARARY Frank， LIVINGESTON Marilynn. Independent Domination in Hypercubes[J]. Applied Mathematics Letters， 1993， 6（3）： 27-28.

[13]师海忠， 牛攀峰. 冒泡排序网络的控制数[J]. 甘肃科学学报， 2010， 22（3）： 32-35.

[14]KLAVZAR Sandi， MA Meijie. The Domination Number of Exchanged Hypercubes[J]. Information Processing Letters， 2014， 114： 159-162.

[15]闫云娟， 徐保根， 冯大一. 两类图的符号控制数[J]. 华东交通大学学报， 2017， 34（6）： 109-115.

[16]师海忠， 杨进霞. 广义b-基超立方体网络的控制数[J]. 计算机科学与应用， 2017， 7（9）： 814-819.