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

關鍵詞： 互連網(wǎng)絡;平衡超立方體;控制數(shù);符號控制數(shù)

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

本文著錄格式：金永麗. 平衡超立方體的控制數(shù)[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）是互連網(wǎng)絡的拓撲結構，由Wang和Huang[3]提出，作為超立方體的變體，它有超立方體及其變體所沒有的特性。例如，維平衡超立方體的直徑不大于維超立方體的直徑，并且每個處理器都有相同鄰點的備份處理器。正因為有這樣的特性，近年來引起了許多學者們的廣泛關注。特別地，Yang[4]證明了平衡超立方體是偶泛連通的;Lü[5]等人得到了平衡超立方體的匹配排除數(shù)和條件匹配排除數(shù);Lü和Wu[6]證明了平衡超立方體有兩個邊不交的哈密爾頓圈。關于其它互連網(wǎng)絡拓撲結構性質(zhì)的研究可參見文獻[7-11]。

圖的控制理論在圖論本身的研究領域應用廣泛，而圖的控制數(shù)是控制理論中的一個基本參數(shù)，因此給出準確的控制數(shù)具有重要的意義。圖的控制數(shù)問題是NPC問題，確定圖的控制數(shù)是比較困難的，所以許多結構復雜的圖的控制數(shù)仍待研究。其中，文獻[12-16]對一些互連網(wǎng)絡的控制數(shù)進行了研究。本文根據(jù)平衡超立方體的性質(zhì)，給出了低維情形下的點控制數(shù)及符號控制數(shù)，提出了一個關于維平衡超立方體點控制數(shù)的問題。

本文的結構如下：第二部分給出了平衡超立方體、控制數(shù)、符號控制數(shù)的定義及本文用到的性質(zhì)和引理;第三部分研究了平衡超立方體的點控制數(shù);第四部分給出了時平衡超立方體的符號控制數(shù)。文中所提及的術語和符號參見文獻[1-2]。

1? 預備知識

下面我們介紹平衡超立方體的定義及其部分性質(zhì)，控制數(shù)和符號控制數(shù)的定義及其相關引理。

分別如圖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]張欣， 師海忠. 交叉立方體連通圈網(wǎng)絡的Hamilton分解[J]. 軟件， 2015， 36（8）： 92-98.

[8]王海鋒， 師海忠. M?bius 超立方體網(wǎng)絡的Hamilton分解[J].軟件， 2015， 36（10）： 85-89.

[9]胡艷紅， 師海忠. 關于冒泡排序連通圈網(wǎng)絡猜想的一個注記[J]. 軟件， 2016， 37（01）： 91-100.

[10]師海忠， 汪生龍. 關于煎餅網(wǎng)絡及層次環(huán)煎餅網(wǎng)絡的幾個猜想[J]. 軟件， 2018， 39（1）： 94-100.

[11]師海忠， 陳璐璐. k次Herschel—師連通圈網(wǎng)絡[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]師海忠， 牛攀峰. 冒泡排序網(wǎng)絡的控制數(shù)[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]閆云娟， 徐保根， 馮大一. 兩類圖的符號控制數(shù)[J]. 華東交通大學學報， 2017， 34（6）： 109-115.

[16]師海忠， 楊進霞. 廣義b-基超立方體網(wǎng)絡的控制數(shù)[J]. 計算機科學與應用， 2017， 7（9）： 814-819.