摘要
研究了两个图G1和G2的强乘积图G1■G2的连通度和边连通度.这里证明了λ(G1■G2)=min{λ1(n2+2m2),λ2(n1+2m1),δ1+δ2+δ1δ2},如果G1和G2都是连通的;还证明了κ(G1■G2)=min{δ1n2,δ2n1,δ1+δ2+δ1δ2},如果G1和G2都是极大连通的.其中,ni,mi,λi和δi分别表示Gi(i=1,2)的阶数、边数、边连通度和最小度.
The strong product graph G1×G2 of two graphs G1 and G2 was considered, and it was proved that λ （G1 × G2 ） = min { λ1 （n2 ＋ 2m2 ）, λ2 （n1＋ 2m1 ）, δ1 ＋ δ2＋δ1δ2} if G1 and G2 were connected, and k （G1 × G2 ） = min{δ1n2 ,δ2n1, δ1＋δ2＋δ1δ2} if G1 and G2 were maximally connected, where hi, mi, λi and δi were the order, the number of edges, the edge-connectivity and the minimum degree of Gi （i=1,2）, respectively.
基金
Supported by NNSF of China (No 10671191)
关键词
连通度
边连通度
强乘积图
connectivity； edge-connectivity
strong product graphs
