Kronecker乘积图的超连通性(英文)  

A Note on the Super Connectivity of Kronecker Product of Graphs

作　　者：郝琛[1] 林辉球[2] 覃城阜[3] 

机构地区：[1]晋中职业技术学院,山西晋中030600 [2]华东师范大学数学科学学院,上海200062 [3]广西师范学院数学科学学院,广西南宁530001

出　　处：《数学研究》2013年第3期253-259,共7页Journal of Mathematical Study

基　　金：supported by NSFC(11171279,1161006);Natural Sciences Foundation of Guangxi Province(2012GXNSFBA053005);the Scientific Research Foundation of Guangxi Education Committee(200103YB069)

摘　　要：设G1和G2是两个连通图,则G1和G2的Kronecker积G1×G2定义如下:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)}.我们证明了G×Kn(n≥4)超连通图当且仅当κ(G)n>δ(G)(n 1),其中G是任意的连通图,Kn是n阶完全图.进一步我们证明了对任意阶至少为3的连通图G,如果κ(G)=δ(G),则G×Kn(n≥3)超连通图.这个结果加强了郭利涛等人的结果.Let G1 and G2 be two connected graphs. The Kronecker product G1 × G2 is the graph with vertex set V（G1 × G2） =V（G1） x V（G2） and the edge set E（G1 × G2） = （（ul,vl）（u2,u2） ： ulu2 ∈ E（G1）,ulu2 ∈ E（G2））. In this note, we show that G × Kn （n 〉 4） is super-k if and only if k（G）n 〉 δ（G）（n - 1）, where G is any connected graph and K,, is the complete of n vertices. Furthermore, we show that for any connected graph G with at least three vertices, if s（G） = 5（G） then G × Kn is super-k for n 〉 3. This result strengthens the known results of Guo et al..

关 键 词：KRONECKER积 连通性 超连通性 

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