超立方體網(wǎng)絡(luò)的限制邊連通性

劉芳，歐見(jiàn)平

?

超立方體網(wǎng)絡(luò)的限制邊連通性

劉芳，歐見(jiàn)平

（五邑大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，廣東 江門(mén) 529020）

超立方體；限制邊連通度；網(wǎng)絡(luò)可靠性

1 超立方體的分解

用和分別表示由的點(diǎn)集對(duì)所有的和對(duì)所有的所導(dǎo)出的子圖. 當(dāng)為偶數(shù)時(shí)，這兩個(gè)子圖都同構(gòu)于圖，即；當(dāng)為奇數(shù)時(shí)，. 不難看出，當(dāng)為偶數(shù)時(shí)，和之間存在一個(gè)完美匹配；同樣的，當(dāng)為奇數(shù)時(shí)，和之間也存在一個(gè)完美匹配. 這兩種情況如圖1描述.

證明 由公式（1）可以得出

所以，引理成立.

引理得證.

.

2）如果為奇數(shù)、為偶數(shù)，由引理2和3得到：

.

3）如果和均為偶數(shù)，由引理2和3得到

.

4）如果為偶數(shù)、為奇數(shù)，那么

.

綜上所述，引理成立.

引理5 如果是超立方體中一個(gè)頂點(diǎn)數(shù)為的子圖，那么.

證明 當(dāng)時(shí)結(jié)論是成立的，證明省略. 當(dāng)時(shí)，令表示由中的頂點(diǎn)集導(dǎo)出的子圖；表示由中的頂點(diǎn)集導(dǎo)出的子圖. 則存在正整數(shù)，使得. 令，不失一般性假設(shè). 設(shè)表示端點(diǎn)分別在和中的邊構(gòu)成的集合. 注意到且，由引理4對(duì)進(jìn)行歸納證明可得：

.

因此，引理成立.

2 限制邊連通度

由公式（1）和引理5易得引理6，證明省略.

引理6 如果有，那么.

.

因此，引理成立.

定理成立.

[1]BONSMA P, UEFFING N, BOLKMNN L. Edge-cuts leaving components of order at least three[J]. Discrete Math, 2002, 256:431-439.

[3]HAJIAGHAYI M T, HAJIAGHAYI M. A note the bounded fragmentation property and its application in network reliability[J]. European J Combin, 2003, 24: 891-896.

[4]HELLWIG A, BOLKMANN L. Maximally edge-connected and vertex-connected graphs and digraphs[J]. Discrete Math, 2008, 308:3265-3296.

[7] OU Jianping. On optimizing edge connectivity of product graphs[J]. Discrete Math, 2011, 311: 478-492.

[8]WANG Ming, LI Qiao. Conditional edge connectivity properties, reliability comparison and transitivity of graphs[J]. Discrete Math, 2002, 258: 205-214.

[9] OU Jianping, ZHANG Fuji. 3-restricted edge connectivity of vertex transitive graphs [J]. Ars Combin, 2005, 74: 291-302.

[10] BONDY J A, MURTY U S R. Graph theory with applications[M]. New York: Elserier, 1976.

Restricted Edge Connectivity of Hypercube Networks

LIUFang, OUJian-ping

(School of Mathematics and Computation Science, Wuyi University, Jiangmen 529020, China)

hypercube; restricted edge connectivity; network reliability

1006-7302（2012）03-0001-05

O157.5

A

2012-05-14

國(guó)家自然科學(xué)基金資助項(xiàng)目（11126326）

劉芳（1985—），女，山東濟(jì)寧人，在讀碩士生，研究方向?yàn)閳D論及其應(yīng)用. 歐見(jiàn)平，教授，博士，碩士生導(dǎo)師，通信作者，研究方向?yàn)閳D論及其應(yīng)用、網(wǎng)絡(luò)的可靠性與容錯(cuò)性、化學(xué)圖論、圖的連通性理論.