Structure connectivity and substructure connectivity of wheel networks

Consider a graph Gand its connected subgraph T. The T-structure connectivity kappa(G; T) of Gis the cardinality of a minimum set of subgraphs in G, whose removal disconnects Gand each element in the set is isomorphic to T. The T-substructure connectivity kappa(s)(G; T) of Gis the cardinality of a minimum set of subgraphs in G, whose removal disconnects Gand each element in the set is isomorphic to a connected subgraph of T. In G, the standard connectivity kappa(G) is regarded as a simplification of both kappa(G; T) and kappa(s)(G; T). The wheel network, denoted by CWn, is an attractive interconnected network prototype for multiple CPU systems. In this paper, we determine kappa(CWn; P2k+1)(resp. kappa(s)(CWn; P2k+1)) for n >= 5and k + 1 <= 2n - 4, kappa(CWn; P-2k)(resp. kappa(s)(CWn; P-2k)) for n >= 6 and k <= 2n - 4and a lower bound of kappa(CWn; C-2k)(resp. kappa(s)(CWn; C-2k)) for n >= 6and k <= 2n - 4. (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

This paper investigates two connectivity metrics in graphs, namely structure connectivity and substructure connectivity, and their relationship with standard connectivity. The connectivity parameters of the wheel network under certain conditions are determined and lower bounds are provided.