The restricted connectivity of complete-transposition networks
Wang Guo-lian · 2013
Complete-transposition networks are a class of important Cayley graphs in networks design.The κ-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 kk(λ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 κ-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≥4,k2(CTn)=n(n-1)-2,k3(CTn)= 3n(n-1)/2-6,when n≥3,λ2(CTn)=n(n-1)-2,λ3(CTn)=3n(n-1)/2-4.