极大3等周边连通图的充分条件

k等周边连通度是一个比边连通度更可靠的网络可靠性参数。 连通图G的k等周边连通度定义为γk(G)=min{［X,X-］:XV(G),X≥k,X-≥k},其中X-=V(G)＼X。令βk(G)=min{［X,X-］:XV(G),X=k}。图G是极大k等周边连通的如果γk(G)=βk(G)。令G是一个阶至少为6的连通图。本文证明了如果对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足N(u)∩N(v)≥2;当u和v中至少有一个在三角形中时满足N(u)∩N(v)≥5,那么G是极大3等周边连通的。

Sufficient conditions of a maximally 3-isoperimetric edge connected graph

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 γk(G)=min{［X,X-］:XV(G),X≥k,X-≥k},where X-=V(G)＼X. Let βk(G)=min{［X,X-］:XV(G),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, N(u)∩N(v)≥2 holds when u and v are not on a triangle. If N(u)∩N(v)≥5 holds for u or v on a triangle, then G is maximally 3 isoperimetric edge connected.