Note on Applications of Linearly Many Faults. (15th November 2019) - Gu, Mei-Mei; Hao, Rong-Xia; Cheng, Eddie
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).