Name
Abstract | ||
|---|---|---|
The r-component connectivity c kappa(r) (G) of a non-complete graph G is the minimum number of vertices whose removal results in a disconnected graph with at least r components. This parameter generalizes the classical connectivity. Hence, it is an important parameter to evaluate the reliability and fault tolerance of a network. Let Gamma(n) be the n-dimensional Cayley graph generated by transposition trees, and g(Gamma(n)) denote the girth of Gamma(n) (i.e., the length of a shortest cycle of Gamma(n)). It has been shown that either g(Gamma(n)) = 4 or g(Gamma(n)) = 6. In this paper, we obtain that c kappa(3)(Gamma(n)) = 2n - 4 if g(Gamma(n)) = 4 and c kappa(3)(Gamma(n)) = 2n - 3 if g(Gamma(n)) = 6 for n >= 4. As corollaries, the 3-component connectivity of the star graph S-n and the bubble-sort graph B-n can be obtained directly. Also, the above consequences explicitly point out that there is a flaw in the recent result of Xu et al., (2020). (C) 2020 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.dam.2020.07.012 | DISCRETE APPLIED MATHEMATICS |
Keywords | DocType | Volume |
Cayley graphs, Transposition tree, Fault-tolerance, Component connectivity | Journal | 287 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shu-Li Zhao | 1 | 1 | 4.40 |
| Jou-Ming Chang | 2 | 546 | 50.92 |
| Rongxia Hao | 3 | 165 | 26.11 |