A Kind of Conditional Connectivity of Cayley Graphs Generated by 2-trees

Abstract

For a connected graph $\mathit{G}\mathbf{=}\mathbf{(}\mathit{V}\mathbf{(}\mathit{G}\mathbf{)},\mathit{E}\mathbf{(}\mathit{G}\mathbf{)}\mathbf{)}$⁠, a subset $\mathit{F}\mathbf{\subset }\mathit{V}(\mathit{G})$ is called an R^k-vertex-cut if $\mathit{G}\mathbf{-}\mathit{F}$ is disconnected and each vertex $\mathit{u}\mathbf{\in }\mathit{V}\mathbf{(}\mathit{G}\mathbf{)}\mathbf{-}\mathit{F}$ has at least k neighbors in $\mathit{G}\mathbf{-}\mathit{F}$⁠. The cardinality of a minimum R^k-vertex-cut of G is the R^k-vertex-connectivity and is denoted by ${\mathit{\kappa }}^{\mathit{k}}\mathbf{(}\mathit{G}\mathbf{)}$⁠. The conditional connectivity is a new measure to study the fault tolerance of network structures beyond connectivity. In this paper, we study R¹-vertex-connectivity and R²-vertex-connectivity of Cayley graphs generated by 2-trees ${\mathit{T}}_{\mathbf{2},\mathit{n}}$⁠, which are denoted by $\mathit{K}{\mathit{T}}_{\mathit{n}}$⁠, and show that ${\mathit{\kappa }}^1\mathbf{(}\mathit{K}{\mathit{T}}_{\mathit{n}}\mathbf{)}\mathbf{=}\mathbf{4}\mathit{n}\mathbf{-}\mathbf{8}$ for $\mathit{n}\mathbf{\ge }\mathbf{4}$⁠; ${\mathit{\kappa }}^{\mathbf{2}}(\mathit{K}{\mathit{T}}_{\mathit{n}}\mathbf{)}\mathbf{=}\mathbf{8}\mathit{n}\mathbf{-}\mathbf{22}$ for $n\ge 6$⁠.