Journal
THEORETICAL COMPUTER SCIENCE
Volume 850, Issue -, Pages 20-29Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2020.10.028
Keywords
Interconnected networks; Structure connectivity; Substructure connectivity; Wheel networks; Paths; Cycles
Categories
Funding
- NSFC [61772010]
- foundation of Inner Mongolia for Nationalities [NMDGP17106]
- 2020 Scientific Research Project for Postgraduates of Henan Normal University [YL202008]
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available