2025/11/03 by Ting Tian, Shumin Zhang, Tian, Ting +3 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #Reliability and Maintenance Optimization
paper · pdf · doi:10.48550/arxiv.2511.01422
openalex publication_date 2025/11/03 · openalex created_date 2025/11/06 · openalex updated_date 2026/07/28
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 \ 1,2,…,n\ and a set T of transpositions of Sym(n). Let G(T) be the graph on vertex set \ 1,2,…,n\ and edge set \ij\colon(ij)∈ T\. If G(T) is a unicyclic triangle free graphs, then denoted the Cayley graph Cay(Sym(n),T) by UGn. As a result, we determine the exact value of cyclic connectivity of UGn as κc(UGn)=4n-8 for n≥ 4 .