两类图的Kronecker积的超连通度

Super Connectivity of Kronecker Product of two Kinds of Graphs

超连通度参数可以度量多处理器系统的可靠性。图G的超连通度κ′(G)是指删除系统中的一些点使得网络不连通,并且每一个连通分支至少有2个顶点,删除这些顶点的最小数目就是超连通度。设G_(1)和G_(2)为两个图,则G_(1)和G_(2)的Kronecker积G_(1)×G_(2)有顶点集V(G_(1)×G_(2))=V(G_(1))×V(G_(2))和边集E(G_(1)×G_(2))=(u_(1),v_(1))(u 2,v_(2)):u_(1)u 2∈E(G_(1)),v_(1)v_(2)∈E(G_(2)).文章证明了完全图k_(n)和顶点集划分为X_(1),X_(2),…,X_(l)的完全多部图T(x_(1),x_(2),…,x_(l))的Kronecker积的超连通度是n(l∑i=1|x_(i)|)-2(|x_(l)-1|+x_(l)),其中X_(i)=x_(i)且x_(1)≤x_(2)≤…≤x_(l).

Super connectivity parameter can measure the reliability of multiprocessor systems.The super connectivityκ′(G)of a graph G refers to deleting some points in the system to make the network disconnected,and every connected branch has at least two vertices.The minimum number of these vertices be deleted is the super connectivity.Let G_(1)and G_(2)be two graphs,then the Kronecker product of G_(1)and G_(2)has the vertex set V(G_(1)×G_(2))=V(G_(1))×V(G_(2))and the edge set E(G_(1)×G_(2))={(u_(1),v_(1)(u_(2),v_(2)):u_(1)u_(2)∈E(G_(1)),v_(1)v_(2)∈E(G_(2))}.This paper prove that the super connectivity of the Kronecker product of complete graphs K_(n)and complete multipartite graphs T(x_(1),x_(2),…,x_(l))with a vertex set divided into X_(1),X_(2),…,X_(l)is n(l∑i=1|x_(i)|)-2(|x_(l)-1|+x_(l)),where X_(i)=x_(i)and x_(1)≤x_(2)≤…≤x_(l).