两类图的Kronecker积的超连通度

作者：马芳玲; 原军^*

来源：太原科技大学学报, 2023, 44(06): 584-588.

• Kronecker积
• 超连通度
• 完全图
• 完全多部图
• 互连网络

超连通度参数可以度量多处理器系统的可靠性。图G的超连通度κ′(G)是指删除系统中的一些点使得网络不连通，并且每一个连通分支至少有2个顶点，删除这些顶点的最小数目就是超连通度。设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)}．文章证明了完全图kn和顶点集划分为X1,X2，…，Xl的完全多部图T(x1,x2，…，xl)的Kronecker积的超连通度是■，其中■且x1≤x2≤…≤xl.

• 单位
  太原科技大学