A kind of conditional connectivity of transposition networks generated by $k$-trees

Abstract

For a graph $G=(V,E)$, a subset $F\subset V(G)$ is called an $R_k$-vertex-cut of $G$ if $G-F$ is disconnected and each vertex $u\in V(G)-F$ has at least $k$ neighbors in $G-F$. The $R_k$-vertex-connectivity of $G$, denoted by ${\kappa }^k(G)$, is the cardinality of the minimum $R_k$-vertex-cut of $G$, which is a refined measure for the fault tolerance of network $G$. In this paper, we study ${\kappa }^2$ for Cayley graphs generated by $k$-trees. Let $Sym(n)$ be the symmetric group on $\{1,2,\cdots ,n\}$ and $\mathcal{T}$ be a set of transpositions of $Sym(n)$. Let $G(\mathcal{T})$ be the graph on $n$ vertices $\{1,2,...,n\}$ such that there is an edge $ij$ in $G(\mathcal{T})$ if and only if the transposition $ij\in \mathcal{T}$. The graph $G(\mathcal{T})$ is called the transposition generating graph of $\mathcal{T}$. We denote by $Cay(Sym(n),\mathcal{T})$ the Cayley graph generated by $G(\mathcal{T})$. The Cayley graph $Cay(Sym(n),\mathcal{T})$ is denoted by $T_k{G}_n$ if $G(\mathcal{T})$ is a $k$-tree. We determine ${\kappa }^2(T_k{G}_n)$ in this work. The trees are $1$-trees, and the complete graph on $n$ vertices is a $n-1$-tree. Thus, in this sense, this work is a generalization of the such results on Cayley graphs generated by transposition generating trees and the complete-transposition graphs.

arXiv comment11pages,2figures