平衡超立方體的控制數(shù)

金永麗

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

關(guān)鍵詞： 互連網(wǎng)絡(luò);平衡超立方體;控制數(shù);符號(hào)控制數(shù)

中圖分類號(hào)： TP393 ???文獻(xiàn)標(biāo)識(shí)碼： 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）是互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，由Wang和Huang[3]提出，作為超立方體的變體，它有超立方體及其變體所沒(méi)有的特性。例如，維平衡超立方體的直徑不大于維超立方體的直徑，并且每個(gè)處理器都有相同鄰點(diǎn)的備份處理器。正因?yàn)橛羞@樣的特性，近年來(lái)引起了許多學(xué)者們的廣泛關(guān)注。特別地，Yang[4]證明了平衡超立方體是偶泛連通的;Lü[5]等人得到了平衡超立方體的匹配排除數(shù)和條件匹配排除數(shù);Lü和Wu[6]證明了平衡超立方體有兩個(gè)邊不交的哈密爾頓圈。關(guān)于其它互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)性質(zhì)的研究可參見(jiàn)文獻(xiàn)[7-11]。

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

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

1 ?預(yù)備知識(shí)

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

定義1[3] ?維平衡超立方體（記作包含個(gè)頂點(diǎn)，其中和。每個(gè)頂點(diǎn) 都有以下個(gè)鄰點(diǎn)：

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

[2]徐保根. 圖的控制與染色理論[M]. 武漢： 華中科技大學(xué)出版社， 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)絡(luò)的Hamilton分解[J]. 軟件， 2015， 36（8）： 92-98.

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

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

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

[11]師海忠， 陳璐璐. k次Herschel—師連通圈網(wǎng)絡(luò)[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)絡(luò)的控制數(shù)[J]. 甘肅科學(xué)學(xué)報(bào)， 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]閆云娟， 徐保根， 馮大一. 兩類圖的符號(hào)控制數(shù)[J]. 華東交通大學(xué)學(xué)報(bào)， 2017， 34（6）： 109-115.

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