摘要
k等周边连通度是一个比边连通度更可靠的网络可靠性参数。连通图G的k等周边连通度定义为γ_k(G)=min{[X,]:X■V(G),X≥k,≥k},其中=V(G)\X。令β_k(G)=min{[X,]:X■V(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等周边连通的。
/c-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 y k( G) = minj | γk(G)=min{[X,]:XV(G),X≥k,≥k},=V(G)/X.βk(G)=min{[X,]:XV(G),X=k}. A graph G is maximally k-isoperimetric edge connected if yk(G) =f3k(G). Let G be a connected graph of at least order 6. We prove that for any pair of nonadjacent vertices u, vinG, |N(u) C| N( v) |≥2 holds when u and v are not on a triangle. If | /V( u) n /V( v) | ≥ 5 holds for u or v on a triangle, then G is maximally 3-isoperimetric edge connected.
出处
《山东科学》
CAS
2016年第4期75-79,共5页
Shandong Science
关键词
互连网络
极大k等周边连通图
k等周边连通度
邻域
interconnection networks
maximally /c-isoperimetric edge connected graph
/c-isoperimetric edgeconnectivity
neighborhood