Reliability assessment of the Cayley graph generated by trees
type: Item
instance of: scholarly article
title: Reliability assessment of the Cayley graph generated by trees
zbMATH Open document ID: 1450.05047
author: Jou-Ming Chang
author: Shu-Li Zhao
author: Rong-Xia Hao
published in: Discrete Applied Mathematics
publication date: 2020-10-14T00:00:00Z
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.
reviewed by: Valeriano Aiello
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 7260812
zbMATH Keywords: Cayley graphs
zbMATH Keywords: transposition tree
zbMATH Keywords: fault-tolerance
zbMATH Keywords: component connectivity
MaRDI profile type: Publication
full work available at URL: j.dam.2020.07.012
OpenAlex ID: W3047233645
cites work: A Generalization of Line Connectivity and Optimally Invulnerable Graphs
cites work: Q5422499
cites work: The 4-component connectivity of alternating group networks
cites work: Two kinds of generalized 3-connectivities of alternating group networks
cites work: Linearly many faults in Cayley graphs generated by transposition trees
cites work: Orienting Cayley graphs generated by transposition trees
cites work: Structural Properties of Generalized Exchanged Hypercubes
cites work: Reliability analysis of Cayley graphs generated by transpositions
cites work: Reliability analysis of twisted cubes
cites work: Q4352273
cites work: Component connectivity of the hypercubes
cites work: Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
cites work: 3-extra connectivity of Cayley graphs generated by transposition generating trees
cites work: Q3765806
cites work: A kind of conditional vertex connectivity of star graphs
cites work: The 1-good-neighbour diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model
cites work: Conditional connectivity of Cayley graphs generated by transposition trees
cites work: Two kinds of generalized connectivity of dual cubes
cites work: Component connectivity of hypercubes
cites work: Component Edge Connectivity of Hypercubes
DOI: 10.1016/J.DAM.2020.07.012
description: scientific article; zbMATH DE number 7260812