平衡超立方體的控制數

金永麗

摘 ?要： 控制數可用于衡量互連網絡的可靠性，而平衡超立方體網絡作為超立方體網絡的變體，有許多優良的性質。因此，根據平衡超立方體的性質，確定了n=1，2，3時平衡超立方體的控制數以及符號控制數的具體值，提出了關于n維平衡超立方體控制數的一個問題。

關鍵詞： 互連網絡;平衡超立方體;控制數;符號控制數

中圖分類號： TP393 ???文獻標識碼： A ???DOI：10.3969/j.issn.1003-6970.2020.09.044

【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[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.