Some conditional vertex connectivities of complete-transposition graphs

A subset F subset of V(G) is called an R-k-vertex-cut if G - F is disconnected and each vertex u is an element of V(G) - F has at least k neighbors in G - F. The cardinality of a minimum R-k-vertex-cut is the R-k-vertex-connectivity of G and is denoted by K-k(G). The conditional connectivity is a measure to study the structure of networks beyond connectivity. Hypercubes form the basic classes of interconnection networks. Complete transposition graphs were introduced to be competitive models of hypercubes. In this paper, we determine the numbers K-1 and K-2 for complete-transposition graphs, K-1(CTn) = n(n - 1) - 2, K-2(CT4) = 16 and K-2(CTn) = 2n(n - 1) - 10 for n >= 5. (C) 2014 Elsevier Inc. All rights reserved.