关键词: interconnection networks, k-isoperimetric edge connectivity, maximally k-isoperimetric edge connected graph, neighborhood

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 γ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.

Key words: maximally k-isoperimetric edge connected graph, k-isoperimetric edge connectivity, neighborhood, interconnection networks