Structure connectivity and substructure connectivity of twisted hypercubes

2018/03/22 by Dong Li, Li, Dong, Xiaolan Hu +3
Computer Science · #Interconnection Networks and Systems #Advanced Graph Theory Research #Cooperative Communication and Network Coding

paper · pdf · doi:10.48550/arxiv.1803.08408

Abstract

Let G be a graph and T a certain connected subgraph of G. The T-structure connectivity κ(G; T) (or resp., T-substructure connectivity κ^s(G; T)) of G is the minimum number of a set of subgraphs F=\T₁, T₂, …, T_m\ (or resp., F=\T^'₁, T^'₂, …, T^'_m\) such that T_i is isomorphic to T (or resp., T^'_i is a connected subgraph of T) for every 1≤ i ≤ m, and F's removal will disconnect G. The twisted hypercube H_n is a new variant of hypercubes with asymptotically optimal diameter introduced by X.D. Zhu. In this paper, we will determine both κ(H_n; T) and κ^s(H_n; T) for T∈\K_1,r, P_k\, respectively, where 3≤ r≤ 4 and 1 ≤ k ≤ n.

Related

• Structure and substructure connectivity of balanced hypercubes
• P_k and C_k structure and substructure connectivity of hypercubes
• Randomly twisted hypercubes -- between structure and randomness
• The restricted h-connectivity of balanced hypercubes
• Structure fault diameter of hypercubes