完全对换网络的限制连通度

完全对换网络是基于 Cayley 图模型的一类重要互连网络. 一个图 G 的 k-限制点(边)连通度是使得 G-F 不连通且每个分支至少有 k 个顶点的最小点(边)子集 F 的基数, 记作 \kappa_{k}(\lambda_{k}). 它是衡量网络可靠性的重要参数之一, 也是图的容错性的一种精化了的度量. 一般地, 网络的 k-限制点(边)连通度越大, 它的连通性就越好. 证明了完全对换网络 CT_{n} 的 2-限制点(边)连通度和 3-限制点(边)连通度, 具体来说: 当 n\geq4 时, \kappa_{2}(CT_{n})=n(n-1)-2, \kappa_{3}(CT_{n})=\frac{3n(n-1)}{2}-6; 当 n\geq3 时, \lambda_{2}(CT_{n})=n(n-1)-2, \lambda_{3}(CT_{n})=\frac{3n(n-1)}{2}-4.

The restricted connectivity of complete-transposition networks

Complete-transposition networks are a class of important Cayley graphs in networks design. The k-restricted vertex(edge)-connectivity of a graph G is the minimum cardinality of a set of vertices (edges) in G whose removal results in disconnected and each component has at least k vertices, denoted by \kappa_{k}(\lambda_{k}). The k-restricted vertex(edge)-connectivity is one of the most parameters to evaluate the reliability of a network, it is also a refined measure of the fault tolerance of the graph. In general, the larger the k-restricted vertex(edge)-connectivity of a network, the more reliable the network. The paper proves that 2-restricted vertex(edge)-connectivity and 3-restricted vertex(edge)-connectivity of complete-transposition networks, that is, when n\geq4, \kappa_{2}(CT_{n})=n(n-1)-2, \kappa_{3}(CT_{n})=\frac{3n(n-1)}{2}-6, when n\geq3, \lambda_{2}(CT_{n})=n(n-1)-2, \lambda_{3}(CT_{n})=\frac{3n(n-1)}{2}-4.