变换图G^(--+)的超边连通性

Super edge-connectivity of transformation graph G^(——+)

如果λ(G)=δ(G),则称图G是极大边连通的;如果G的最小边割只能分离G的一个孤立点,则称图G是超边连通的.证明了对所有的有限图G,其变换图G--+都是极大边连通的,G--+是超边连通的当且仅当G不同构于K1,2也不同构于K2∪K1.

A graph G is called maximally edge-connected if λ （G） =δ（G） and it is said to be super edge-connected if every minimal edge-cut-set of size δ （G） separates only one isolated point of G. It is proved that for any graph G, G^-- ＋ is maximally edge-connected and that G^-- ＋ is super edge-connected if and only if G is neither isomorphic to K1,2 nor K2 ∪ K1.