Structure connectivity and substructure connectivity of bubble-sort star graph networks

Guozhen Zhang, Dajin Wang

Research output: Contribution to journalArticleResearchpeer-review

Abstract

The bubble-sort star graph, denoted BSn, is an interconnection network model for multiprocessor systems, which has attracted considerable interest since its first proposal in 1996 [5]. In this paper, we study the problem of structure/substructure connectivity in bubble-sort star networks. Two basic but important structures, namely path Pi and cycle Ci, are studied. Let T be a connected subgraph of graph G. The T-structure connectivity κ(G; T) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to T. The T-substructure connectivity κs(G; T) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to a connected subgraph of T. Both T-structure connectivity and T-substructure connectivity are a generalization of the classic notion of node-connectivity. We will prove that for P2k+1, a path on odd nodes (resp. P2k, a path on even nodes), [Formula presented] for n ≥ 4 and k+1≤2n−3 (resp. [Formula presented] for n ≥ 5 and k≤2n−3). For a cycle on 2k nodes C2k (there are only cycles on even nodes in BSn), κ(BSn;C2k)=κs(BSn;C2k)=⌈[Formula presented] for n ≥ 5 and 2≤k≤n−1.

Original languageEnglish
Article number124632
JournalApplied Mathematics and Computation
Volume363
DOIs
StatePublished - 15 Dec 2019

Fingerprint

Bubble sort
Star Graph
Substructure
Stars
Connectivity
Subgraph
T-structure
Vertex of a graph
Cycle
Path
Deletion
Cardinality
Isomorphic
Interconnection Networks
Multiprocessor Systems
Pi
Network Model
Star
Odd
Graph in graph theory

Keywords

  • Bubble-sort star graphs
  • Cycles
  • Interconnection networks
  • Paths
  • Structure connectivity
  • Substructure connectivity

Cite this

@article{3d7892887fe244118baa5121657cad83,
title = "Structure connectivity and substructure connectivity of bubble-sort star graph networks",
abstract = "The bubble-sort star graph, denoted BSn, is an interconnection network model for multiprocessor systems, which has attracted considerable interest since its first proposal in 1996 [5]. In this paper, we study the problem of structure/substructure connectivity in bubble-sort star networks. Two basic but important structures, namely path Pi and cycle Ci, are studied. Let T be a connected subgraph of graph G. The T-structure connectivity κ(G; T) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to T. The T-substructure connectivity κs(G; T) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to a connected subgraph of T. Both T-structure connectivity and T-substructure connectivity are a generalization of the classic notion of node-connectivity. We will prove that for P2k+1, a path on odd nodes (resp. P2k, a path on even nodes), [Formula presented] for n ≥ 4 and k+1≤2n−3 (resp. [Formula presented] for n ≥ 5 and k≤2n−3). For a cycle on 2k nodes C2k (there are only cycles on even nodes in BSn), κ(BSn;C2k)=κs(BSn;C2k)=⌈[Formula presented] for n ≥ 5 and 2≤k≤n−1.",
keywords = "Bubble-sort star graphs, Cycles, Interconnection networks, Paths, Structure connectivity, Substructure connectivity",
author = "Guozhen Zhang and Dajin Wang",
year = "2019",
month = "12",
day = "15",
doi = "10.1016/j.amc.2019.124632",
language = "English",
volume = "363",
journal = "Applied Mathematics and Computation",
issn = "0096-3003",
publisher = "Elsevier Inc.",

}

Structure connectivity and substructure connectivity of bubble-sort star graph networks. / Zhang, Guozhen; Wang, Dajin.

In: Applied Mathematics and Computation, Vol. 363, 124632, 15.12.2019.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Structure connectivity and substructure connectivity of bubble-sort star graph networks

AU - Zhang, Guozhen

AU - Wang, Dajin

PY - 2019/12/15

Y1 - 2019/12/15

N2 - The bubble-sort star graph, denoted BSn, is an interconnection network model for multiprocessor systems, which has attracted considerable interest since its first proposal in 1996 [5]. In this paper, we study the problem of structure/substructure connectivity in bubble-sort star networks. Two basic but important structures, namely path Pi and cycle Ci, are studied. Let T be a connected subgraph of graph G. The T-structure connectivity κ(G; T) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to T. The T-substructure connectivity κs(G; T) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to a connected subgraph of T. Both T-structure connectivity and T-substructure connectivity are a generalization of the classic notion of node-connectivity. We will prove that for P2k+1, a path on odd nodes (resp. P2k, a path on even nodes), [Formula presented] for n ≥ 4 and k+1≤2n−3 (resp. [Formula presented] for n ≥ 5 and k≤2n−3). For a cycle on 2k nodes C2k (there are only cycles on even nodes in BSn), κ(BSn;C2k)=κs(BSn;C2k)=⌈[Formula presented] for n ≥ 5 and 2≤k≤n−1.

AB - The bubble-sort star graph, denoted BSn, is an interconnection network model for multiprocessor systems, which has attracted considerable interest since its first proposal in 1996 [5]. In this paper, we study the problem of structure/substructure connectivity in bubble-sort star networks. Two basic but important structures, namely path Pi and cycle Ci, are studied. Let T be a connected subgraph of graph G. The T-structure connectivity κ(G; T) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to T. The T-substructure connectivity κs(G; T) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to a connected subgraph of T. Both T-structure connectivity and T-substructure connectivity are a generalization of the classic notion of node-connectivity. We will prove that for P2k+1, a path on odd nodes (resp. P2k, a path on even nodes), [Formula presented] for n ≥ 4 and k+1≤2n−3 (resp. [Formula presented] for n ≥ 5 and k≤2n−3). For a cycle on 2k nodes C2k (there are only cycles on even nodes in BSn), κ(BSn;C2k)=κs(BSn;C2k)=⌈[Formula presented] for n ≥ 5 and 2≤k≤n−1.

KW - Bubble-sort star graphs

KW - Cycles

KW - Interconnection networks

KW - Paths

KW - Structure connectivity

KW - Substructure connectivity

UR - http://www.scopus.com/inward/record.url?scp=85070529963&partnerID=8YFLogxK

U2 - 10.1016/j.amc.2019.124632

DO - 10.1016/j.amc.2019.124632

M3 - Article

VL - 363

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

SN - 0096-3003

M1 - 124632

ER -