4等周边连通图的邻域条件

Neighborhood Conditions for 4-Isoperimetric Edge Connected Graphs

k等周边连通度是一个比边连通度更可靠的网络可靠性参数.连通图G的k等周边连通度定义为γ_k(G)=min{|[X,X]|:X■V(G),|X|≥k,|X|≥k},其中珡X=V(G)\X.令βk(G)=min{|[X,X]|:X■V(G),|X|=k}.图G是γ_k-最优的如果γ_k(G)=βk(G).令G是一个阶至少为8的图.文章证明了如果对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足N(u)∩N(v)≥3;当u和v中至少有一个在三角形中时满足N(u)∩N(v)≥7,那么G是γ4-最优的.

The k-isoperimetric edge connectivity is a more refined network reliability index than edge connectivity.The k-isoperimetric edge connectivity of a connected graph Gis defined as γ_k（G）=min{｜[X,X]｜：X■V（G）,｜X｜≥k,｜X｜≥k},where X=V（G）／X.Let β_k（G）=min{｜[X,X]｜：X■V（G）,｜X｜=k}.A graph Gis called γ_k-optimal graph ifγ_k（G）=βk（G）.Let Gbe agraph of order at least 8.This paper shows that for any pair u,v of nonadjacent vertices in G,if N（u）∩N（v） ≥3 when neither unor vlies on a triangle,or N（u）∩N（v） ≥7when uor lies v on a triangle,then Gisγ4-optimal.