图的运算和超边连通度

许多网络拓朴结构是通过图的运算得到的.超边连通性是衡量网络可靠性的一个重要尺度.一个图G为最优-λ'图,如果其限制性边连通度λ'(G)等于其最小边度ζ(G).一个最优-λ′图被称为超-λ'图,如果从G中去掉任何一个最小限制性边割都会产生孤立边.考虑图的三类运算;证明了如果原始图为正则的最优-λ'图,则运算后的图是超-λ'图.

Graph Operations and Super Edge Connectivity

Many attractive network topologies can be obtained from graph operations. Super edge connectivity is an important measure of network reliability. A graph G is λ'-optimal if the restricted edge connectivity λ' (G) equals to the minimum edge degree ζ(G), and super-λ' if every minimum restricted edge cut of G isolates an edge. Three classes of graph operations are considered,and it is shown that if the original graphs are regular and λ′-optimal,then their operation results in a super-λ' graph.