張倩華，林上為

(山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006)

廣義超立方體的廣義連通度

張倩華，林上為

(山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006)

k元n方體是著名的超立方體網(wǎng)絡(luò)的推廣。針對(duì)k元n方體的廣義3-連通度問題，證明了對(duì)任意的整數(shù)k≥3和n≥1，k元n方體中存在2n-1棵內(nèi)部不交的連接任意3個(gè)頂點(diǎn)的樹。

超立方體；連通度；可靠性；樹；路

0 引言

連通度是圖論的核心內(nèi)容之一，廣義連通度作為連通度的一個(gè)推廣，被廣泛運(yùn)用于互連網(wǎng)絡(luò)中，可用來測量網(wǎng)絡(luò)的可靠性。近年來，很多圖的廣義連通度已經(jīng)得到研究[7-8]。然而，k元n方體的廣義連通度研究較少。本文將在k≥3的條件下，確定k元n方體的廣義3-連通度。

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

V={x1x2…xn:xi∈{0,1,2,…,k-1},i=1,2,…,n}。

定義2[9]給定一個(gè)圖G和G的頂點(diǎn)子集X，若G-X不連通或平凡，則稱X為G的一個(gè)頂點(diǎn)割。G的連通度κ(G)是G中最小頂點(diǎn)割的頂點(diǎn)個(gè)數(shù)。

熟知連通度有如下的等價(jià)定義：

定義3[9]對(duì)V(G)的每個(gè)2元子集S={x,y}，用κ(S)表示G中內(nèi)部不交的(x,y)-路的最大數(shù)目。圖G的連通度κ(G)=min{κ(S):S是V(G)的一個(gè)2元子集}。

連通的無圈圖稱為樹，路是特殊的樹。

注意，κ2(G)=κ(G)，因此，廣義連通度是連通度的一個(gè)推廣。而κn(G)恰恰就是G中邊不相交的生成樹的最大數(shù)目。廣義連通度不僅是一個(gè)自然的組合度量，而且它在實(shí)際應(yīng)用中也可以激發(fā)人們的興趣。近年來，圖的廣義連通度已經(jīng)得到很多研究[9-10]。

定理2[10]n維超立方體Qn的廣義3-連通度為n-1，即κ3(Qn)=n-1。

下面的兩個(gè)引理將在主要結(jié)論的證明中用到。

引理1[9]給定圖G和G中的一個(gè)頂點(diǎn)x。若κ(G)=k，則對(duì)G中任意k個(gè)頂點(diǎn)y1,y2,…,yk，G都含(x,y1)-路P1，(x,y2)-路P2，…，(x,yk)-路Pk，使得對(duì)所有的i≠j有V(Pi)∩V(Pj)={x}。

2 主要定理及其證明

情形1 x,y,z∈V0。

情形2 x,y∈V0,z∈Vp，其中p∈{1,2,…,k-1}。

情形3x∈V0,y∈Vp,z∈Vq，其中p,q∈{1,2,…,k-1}且p≠q。

情形3.1k≥4。

情形3.2k=3。

當(dāng)n=2時(shí)，2n-1=3，3棵內(nèi)部不交的S-樹分別為：T1=(00,01,11,21,22),T2=(00,02,12,22)+(12,11),T3=(00,10,20,22)+(10,11)。

3 結(jié)束語

[1] 徐俊明.組合網(wǎng)絡(luò)理論[M].北京:科學(xué)出版社,2007.

[2] 徐保根,張亞瓊,湯友良.關(guān)于圖的符號(hào)邊控制數(shù)的一些結(jié)論[J].河南科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,33(4):74-77.

[3] ESFAHANIAN A H.Generalized measures of falut tolerance with application ton-cube networks[J].IEEE transactions on computers,1989,38(11):1586-1591.

[4] WANG S Y,LI J,YANG Y X.Unchanging the diameter ofk-aryn-cube networks with faulty vertices[J].International journal of computer mathematics,2015,92(1):15-28.

[5] GU M M,HAO R X,LIU J B.On the extraconnectivity ofk-aryn-cube networks[J/OL].International journal of computer mathematics,2015.[2016-07-20].http://dx.doi.org/10.1080/00207160.2015.109107.

[6] WANG F,ZHANG H.Matchings extend to Hamiltonian cycles ink-aryn-cubes[J].Information sciences,2015,305:1-13.

[7]KOH K M,DONG F M,NG K L,et al.Graph theory:undergraduate mathematics[M].Singapore:World Scientific Publishing,2015.

[8] LI H Z,LI X L,SUN Y F.The generalized 3-connectivity of Cartesian product graphs[J].Discrete mathematics and theoretical computer science,2012,14:43-54.

[9] CHARTRAND G,OKAMOTO F,ZHANG P.Rainbow trees in graphs and generalized connectivity[J].Networks,2010,55:360-367.

[10] LI S S,LI X L,ZHOU W L.Sharp bounds for the generalized connectivityκ3(G)[J].Discrete mathematics,2010,310:2147-2163.

國家自然科學(xué)基金項(xiàng)目(61202017);中國博士后基金項(xiàng)目(2012M510579)

張倩華(1992- ),女，山西長治人，碩士生;林上為(1981-),男,浙江溫州人,副教授,博士，碩士生導(dǎo)師,主要研究方向?yàn)閳D論及其應(yīng)用.

2016-08-12

1672-6871(2017)04-0090-04

10.15926/j.cnki.issn1672-6871.2017.04.018

O157.5

A