强乘积图的连通度和边连通度(英文)  

Connectivity and edge-connectivity of strong product graphs

作　　者：杨超[1] 徐俊明[1] 

机构地区：[1]中国科学技术大学数学系,安徽合肥230026

出　　处：《中国科学技术大学学报》2008年第5期449-455,共7页JUSTC

基　　金：Supported by NNSF of China (No 10671191)

摘　　要：研究了两个图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.

关 键 词：连通度 边连通度 强乘积图 

分 类 号：O157.5[理学—数学]