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

徐子鈞,張磊

(晉中學(xué)院數(shù)學(xué)學(xué)院, 山西 晉中 030600)

?

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

徐子鈞,張磊*

(晉中學(xué)院數(shù)學(xué)學(xué)院, 山西 晉中 030600)

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

關(guān)鍵詞：互連網(wǎng)絡(luò);極大k等周邊連通圖;k等周邊連通度;鄰域

1　引言

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

令

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

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

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

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

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

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

2　主要結(jié)論

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

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

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

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

當(dāng)u,v至少有一個在三角形中時，滿足

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

=0。

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

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

≥3,

則

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

=1,

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

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

=3,

矛盾。

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

=2。

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

=3,

矛盾。

由定理2.2,我們?nèi)菀椎玫较旅娴慕Y(jié)論。

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

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

參考文獻(xiàn)：

[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-)，女，碩士，助教，研究方向為圖論及其應(yīng)用。Emali: huayuycdi@yeah.net

*通信作者。

中圖分類號：O157.6

文獻(xiàn)標(biāo)識碼：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