Reliability assessment of the Cayley graph generated by trees (Q2004067)

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.