Graph connectivity serves as a fundamental metric for evaluating the reliability and fault tolerance of interconnection networks. To more precisely characterize network robustness, the concept of cyclic connectivity has been introduced, requiring that there are at least two components containing cycles after removing the vertex set. This property ensures the preservation of essential cyclic communication structures under faulty conditions. Cayley graphs exhibit several ideal properties for interconnection networks, which permits identical routing protocols at all vertices, facilitates recursive constructions, and ensures operational robustness. In this paper, we investigate the cyclic connectivity of Cayley graphs generated by unicyclic triangle free graphs. Given an symmetric group $Sym(n)$ on $\left\{ 1,2,\dots,n\right\}$ and a set $\mathcal{T}$ of transpositions of $Sym(n)$. Let $G(\mathcal{T})$ be the graph on vertex set $\left\{ 1,2,\dots,n\right\}$ and edge set $\left\{ij\colon(ij)\in \mathcal{T}\right\}$. If $G(\mathcal{T})$ is a unicyclic triangle free graphs, then denoted the Cayley graph Cay$(Sym(n),\mathcal{T})$ by $UG_{n}$. As a result, we determine the exact value of cyclic connectivity of $UG_{n}$ as $κ_{c}(UG_{n})=4n-8$ for $n\ge 4 $.
翻译:图连通性是评估互连网络可靠性与容错能力的基本度量指标。为更精确地表征网络鲁棒性,循环连通性概念被提出,要求在移除顶点集后至少存在两个包含环路的连通分量。该性质确保了在故障条件下关键循环通信结构的保持。Cayley图展现出若干适用于互连网络的理想特性:允许所有顶点采用相同路由协议、便于递归构造,并能保障运行鲁棒性。本文研究了由无三角形单圈图生成的Cayley图的循环连通性。给定对称群$Sym(n)$作用于集合$\left\{ 1,2,\dots,n\right\}$,以及$Sym(n)$中对换构成的集合$\mathcal{T}$。令$G(\mathcal{T})$为以$\left\{ 1,2,\dots,n\right\}$为顶点集、$\left\{ij\colon(ij)\in \mathcal{T}\right\}$为边集的图。若$G(\mathcal{T})$为无三角形单圈图,则将Cayley图Cay$(Sym(n),\mathcal{T})$记作$UG_{n}$。研究结果表明,当$n\ge 4$时,$UG_{n}$的循环连通性精确值为$κ_{c}(UG_{n})=4n-8$。