-
Views
-
Cite
Cite
Mei-Mei Gu, Rong-Xia Hao, Eddie Cheng, Note on Applications of Linearly Many Faults, The Computer Journal, Volume 63, Issue 9, September 2020, Pages 1406–1416, https://doi.org/10.1093/comjnl/bxz088
- Share Icon Share
Abstract
Most graphs have this property: after removing a linear number of vertices from a graph, the surviving graph is either connected or consists of a large connected component and small components containing a small number of vertices. This property can be applied to derive fault-tolerance related network parameters: extra edge connectivity and component edge connectivity. Using this general property, we obtained the |$h$|-extra edge connectivity and |$(h+2)$|-component edge connectivity of augmented cubes, Cayley graphs generated by transposition trees, complete cubic networks (including hierarchical cubic networks), generalized exchanged hypercubes (including exchanged hypercubes) and dual-cube-like graphs (including dual cubes).