Reliability assessment of the Cayley graph generated by trees

DOI10.1016/J.DAM.2020.07.012MaRDI QIDQ2004067zbMATH OpenOpenAlexFDO

Authors Jou-Ming Chang, Shu-Li Zhao, Rong-Xia Hao

Publication date 14 October 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2020.07.012

zbMATH Keywords

Cayley graphscomponent connectivityfault-tolerancetransposition tree

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Connectivity (05C40)

Review text

The connectivity of a graph is the minimum number of vertices whose removal disconnects the graph. In the article under review, the authors study a generalisation of this notion. Let \(G\) be a non-complete graph. For any \(r\) in \(\mathbb{N}\), the \(r\)-component connectivity \(ck_r(G)\) is the minimum number of vertices, whose removal yields a graph with \(r\) components. Clearly, it holds \(ck_{r+1}(G)\leq ck_r(G)\) for all \(r\in\mathbb N\) and when \(r=1\) this reduces to the notion of connectivity. In this article, the authors study Cayley graphs of special type. Consider the symmetric group Sym\((n)\) and let \(T\) be a set of transpositions. The graph \(G(T)\) is a graph with \(n\) vertices (labelled by \(\{1, \ldots, n\}\)) and with an edge \(\overline{ij}\) if and only if the transposition \((ij)\) is in \(T\). If \(G(T)\) is a tree, it is called a transposition tree and \(\Gamma_n:=\mathrm{Cay}(\mathrm{Sym}(n), T)\) is called the Cayley graph generated by a transposition tree. Now let \(\Gamma_n\) be the \(n\)-dimensional Cayley graph generated by a transposition trees and denote by \(g(\Gamma_n)\) the girth of \(\Gamma_n\), that is the length of the shortest cycle of \(\Gamma_n\). The girth of \(\Gamma_n\) may assume only two values: \(4\) or \(6\). The authors of this paper prove that, for \(n\geq 4\), in the former case it holds \(ck_3(\Gamma_n)=2n-4\), while in the latter \(ck_3(\Gamma_n)=2n-3\). As a consequence, the \(3\)-component connectivity of the star graph \(S_n\) and of the bubble-sort graph \(B_n\) are computed.

Recommendations

• Conditional connectivity of Cayley graphs generated by transposition trees
• A kind of conditional connectivity of transposition networks generated by k-trees
• The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles
• 3-extra connectivity of Cayley graphs generated by transposition generating trees
• The generalized 3-connectivity of star graphs and bubble-sort graphs

Cites work

• 3-extra connectivity of Cayley graphs generated by transposition generating trees
• A Generalization of Line Connectivity and Optimally Invulnerable Graphs
• A kind of conditional vertex connectivity of star graphs
• Component connectivity of hypercubes
• Component connectivity of the hypercubes
• Component edge connectivity of hypercubes
• Conditional connectivity of Cayley graphs generated by transposition trees
• Graph theory
• scientific article; zbMATH DE number 4023324 (Why is no real title available?)
• scientific article; zbMATH DE number 1054728 (Why is no real title available?)
• Linearly many faults in Cayley graphs generated by transposition trees
• Orienting Cayley graphs generated by transposition trees
• Reliability analysis of Cayley graphs generated by transpositions
• Reliability analysis of twisted cubes
• Structural properties of generalized exchanged hypercubes
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• The 1-good-neighbour diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model
• The 4-component connectivity of alternating group networks
• Two kinds of generalized 3-connectivities of alternating group networks
• Two kinds of generalized connectivity of dual cubes

Cited in

(16)

• Conditional connectivity of Cayley graphs generated by transposition trees
• The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles
• Component conditional fault tolerance of hierarchical folded cubic networks
• Reliability evaluation of DQcube based on g-good neighbor and g-component fault pattern
• \(h\)-extra \(r\)-component connectivity of interconnection networks with application to hypercubes
• r-component diagnosability of hypercubes under the PMC model
• Extra (component) connectivity and diagnosability of bubble sort networks
• 3-extra connectivity of Cayley graphs generated by transposition generating trees
• Cyclic vertex-connectivity of Cayley graphs generated by transposition trees
• scientific article; zbMATH DE number 4065011 (Why is no real title available?)
• Tree connectivities of Cayley graphs on abelian groups with small degrees
• The generalized 3-connectivity of complete-transposition graphs
• 3-path-connectivity of Cayley graphs generated by transposition trees
• Reliability evaluation for a class of recursive match networks
• Path survival reliabilities as measures of reliability for lifeline utility networks
• Fault-tolerability analysis of hypercubes based on 3-component path-structure connectivity

This page was built for publication: Reliability assessment of the Cayley graph generated by trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2004067)