Kronecker乘积图的超连通性

作者：郝琛; 林辉球; 覃城阜

来源：数学研究, 2013, 46(3): 253-259.

DOI：10.3969/j.issn.1006-6837.2013.03.005

• Kronecker积
• 连通性
• 超连通性

设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×K n(n≥4)超连通图当且仅当κ(G)n＞δ(G)(n-1),其中G是任意的连通图,Kn是n阶完全图.进一步我们证明了对任意阶至少为3的连通图G,如果κ(G)=δ(G),则G×Kn(n≥3)超连通图.这个结果加强了郭利涛等人的结果.

• 单位
  南宁师范大学; 晋中职业技术学院; 华东师范大学