Structure connectivity and substructure connectivity of twisted hypercubes

摘要

Let G be a graph and T a certain connected subgraph of G. The T-structure connectivity kappa(G; T) (or resp., T-substructure connectivity kappa(s)(G; T)) of G is the minimum number of a set of subgraphs F = {T-1, T-2, ..., T-m} (or resp., F = {T-1', T-2', ..., 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 Zhu. In this paper, we will determine both kappa(H-n; T) and kappa(s) (H-n; T) for T is an element of P-k}, respectively, where 3 <= r <= 4 and 1 <= k <= n. (C) 2019 Elsevier B.V. All rights reserved.