简介:设Gl和岛是两个连通图,则G1和G2的Kronecker积GIXG2定义如下:V(G1×G2)=V(G1)×V(G2),E(G1×G2)=((ul,vl)(u2,u2):ulu2∈E(G1),ulu2∈.E(G2)).我们证明了G×Kn(n〉4)超连通图当且仅当k(G)n〉6(G)(n-1),其中G是任意的连通图,Kn是n阶完全图.进一步我们证明了对任意阶至少为3的连通图G,如果圪(G)=δ(G),则G×Kn(n〉3)超连通图.这个结果加强了郭利涛等人的结果.
简介:一个r-klee-图递归定义为一个r+1阶完全图或者通过用一个r阶完全图替换已知的r-klee-图G′中的一个顶点所得到的图.本文主要研究了r-klee-图的Hamilton-连通性和着色问题.我们证明了:每一个r-klee-图是Hamilton-连通的和它的色数是r;如果r是奇数,则它的边色数是r;如果r是偶数,则它的边色数是r+1.