極大3等周邊連通圖的充分條件

徐子鈞,張磊

(晉中學院數學學院, 山西 晉中 030600)

?

極大3等周邊連通圖的充分條件

徐子鈞,張磊*

(晉中學院數學學院, 山西 晉中 030600)

摘要：k等周邊連通度是一個比邊連通度更可靠的網絡可靠性參數。 連通圖G的k等周邊連通度定義為:X?≥k},其中=V(G)X。令:X?=k}。圖G是極大k等周邊連通的如果γk(G)=βk(G)。令G是一個階至少為6的連通圖。本文證明了如果對于G中任意一對不相鄰的頂點u,v,當u和v都不在三角形中時滿足≥2;當u和v中至少有一個在三角形中時滿足≥5,那么G是極大3等周邊連通的。

關鍵詞：互連網絡;極大k等周邊連通圖;k等周邊連通度;鄰域

1　引言

定義1.1設k是一個正整數,G是一個階至少為2k的連通圖。G的k等周邊連通度定義為:

令

顯然,γk(G)≤βk(G)。 2007年,Zhang等[8]給出了極大k等周邊連通圖的定義。

定義1.2設k是一個正整數, G是一個階υ≥2k的連通圖。如果γk(G)=βk(G), 那么稱G是極大k等周邊連通的。

2009年,Wang等[9]給出了一個極大k等周邊圖的鄰域條件。

定理1.4[9]設k是一個正整數, G是一個階至少為2k的圖。如果對G中任意兩個不相鄰頂點u,v都有

那么G是極大k等周邊連通圖。

本文將給出極大3等周邊連通圖的鄰域條件, 這個結果在k=3時, 改進了定理1.4。

2　主要結論

(1)如果在X中存在一個基數為k的子集U使得

那么G是極大k等周邊連通的。

(2)X中不存在基數為k的子集U使得

定理2.2設G是一個階至少為6的連通圖。如果對于G中任意不相鄰的頂點u和v,當u,v都不在三角形中時，滿足

當u,v至少有一個在三角形中時，滿足

那么G是極大3等周邊連通的。

=0。

由引理2.1(1)知,G是極大3等周邊連通的。

由引理2.1(1)知,G是極大3等周邊連通的。

≥3,

則

由引理2.1(1)知,G是極大3等周邊連通的。

=1,

與假設矛盾。因此,X0=?。設H2為G[X]中包含{x1}∪X1中盡可能多的點且包含邊的數目最多的3階子圖。

由引理2.1(1)知,G是極大3等周邊連通的。

=3,

矛盾。

易知X1{x1}≠?。注意到N(u1)∩X={x1}。則對于任意的v∈X{x1},v與u1都不相鄰。根據題意,我們有

=2。

由引理2.1(1)知,G是極大3等周邊連通的。

=3,

矛盾。

由定理2.2,我們容易得到下面的結論。

推論2.3設G是一個階至少為6的無三角形連通圖。如果對于G中任意一對不相鄰的頂點u,v都有

那么G是極大3等周邊連通的。

參考文獻：

[1]BONDY J A,MURTY U S R. Graph Theory[M].New York:Springer,2008.

[3]WANG MING,LI QIAO.Conditional edge connectivity properties, reliability comparisons and transitivity of graphs[J]. Discrete Mathematics, 2002, 258(1/2/3): 205-214.

[4]LI Q,LI Q.Reliability analysis of circulant graphs[J]. Networks, 1998,31(2): 61-65.

[5]XU J M,XU K L.On restricted edge-connectivity of graphs[J]. Discrete Mathematics, 2002, 243(1/2/3): 291-298.

[6]BOESCH F T. On unreliability polynomials and graph connectivity in reliable network synthesis[J]. Journal of Graph Theory, 1986, 10(3): 339-352.

[8]ZHANG Z,YUAN J J.Degree conditions for restricted-edge-connectivity and isoperimetric-edge-connectivity to be optimal[J]. Discrete Mathematics, 2007, 307(2): 293-298.

[9]WANG S Y,LIN S W,LI C F.Sufficient conditions for super k-restricted edge connectivity in graphs of diameter 2[J]. Discrete Mathematics, 2009, 309(9): 908-919.

DOI:10.3976/j.issn.1002-4026.2016.04.015

收稿日期：2015-10-19

作者簡介：徐子鈞(1987-)，女，碩士，助教，研究方向為圖論及其應用。Emali: huayuycdi@yeah.net

*通信作者。

中圖分類號：O157.6

文獻標識碼：A

文章編號：1002-4026(2016)04-0075-05

Sufficient conditions of a maximally 3-isoperimetric edge connected graph

XU Zi-jun,ZHANG Lei*

(School of Mathematics, Jinzhong University, Jinzhong 030600, China)

Abstract∶k-isoperimetric edge connectivity is a more reliable network reliability index than edge connectivity. k-isoperimetric edge connectivity of a connected graph G is defined as :X?≥k},where =V(G)X. Let :X?=k}. A graph G is maximally k-isoperimetric edge connected if γk(G)=βk(G). Let G be a connected graph of at least order 6. We prove that for any pair of nonadjacent vertices u,v in G, ≥2 holds when u and v are not on a triangle. If ≥5 holds for u or v on a triangle, then G is maximally 3-isoperimetric edge connected.Key words∶interconnection networks; maximally k-isoperimetric edge connected graph; k-isoperimetric edge connectivity; neighborhood