Structure connectivity and substructure connectivity of hypercubes

Cheng Kuan Lin, Lili Zhang, Jianxi Fan, Dajin Wang

Research output: Contribution to journalArticle

19 Citations (Scopus)

Abstract

The connectivity of a network - the minimum number of nodes whose removal will disconnect the network - is directly related to its reliability and fault tolerability, hence an important indicator of the network's robustness. In this paper, we extend the notion of connectivity by introducing two new kinds of connectivity, called structure connectivity and substructure connectivity, respectively. Let H be a certain particular connected subgraph of G. The H-structure connectivity of graph G, denoted κ(G;H), is the cardinality of a minimal set of subgraphs F={H1',H2',. . .,Hm'} in G, such that every Hi'∈F is isomorphic to H, and F's removal will disconnect G. The H-substructure connectivity of graph G, denoted κs(G;H), is the cardinality of a minimal set of subgraphs F={J1, J2, . . ., Jm}, such that every Ji∈F is a connected subgraph of H, and F's removal will disconnect G. In this paper, we will establish both κ(Qn;H) and κs(Qn;H) for the hypercube Qn and H∈{K1, K1,1, K1,2, K1,3, C4}.

Original languageEnglish
Pages (from-to)97-107
Number of pages11
JournalTheoretical Computer Science
Volume634
DOIs
StatePublished - 27 Jun 2016

Fingerprint

Substructure
Hypercube
Connectivity
Subgraph
Minimal Set
Cardinality
Graph in graph theory
Fault
Isomorphic
Robustness
Vertex of a graph

Keywords

  • Hypercube
  • Structure connectivity
  • Substructure connectivity

Cite this

Lin, Cheng Kuan ; Zhang, Lili ; Fan, Jianxi ; Wang, Dajin. / Structure connectivity and substructure connectivity of hypercubes. In: Theoretical Computer Science. 2016 ; Vol. 634. pp. 97-107.
@article{f11902d865ba498592bf1989caabf047,
title = "Structure connectivity and substructure connectivity of hypercubes",
abstract = "The connectivity of a network - the minimum number of nodes whose removal will disconnect the network - is directly related to its reliability and fault tolerability, hence an important indicator of the network's robustness. In this paper, we extend the notion of connectivity by introducing two new kinds of connectivity, called structure connectivity and substructure connectivity, respectively. Let H be a certain particular connected subgraph of G. The H-structure connectivity of graph G, denoted κ(G;H), is the cardinality of a minimal set of subgraphs F={H1',H2',. . .,Hm'} in G, such that every Hi'∈F is isomorphic to H, and F's removal will disconnect G. The H-substructure connectivity of graph G, denoted κs(G;H), is the cardinality of a minimal set of subgraphs F={J1, J2, . . ., Jm}, such that every Ji∈F is a connected subgraph of H, and F's removal will disconnect G. In this paper, we will establish both κ(Qn;H) and κs(Qn;H) for the hypercube Qn and H∈{K1, K1,1, K1,2, K1,3, C4}.",
keywords = "Hypercube, Structure connectivity, Substructure connectivity",
author = "Lin, {Cheng Kuan} and Lili Zhang and Jianxi Fan and Dajin Wang",
year = "2016",
month = "6",
day = "27",
doi = "10.1016/j.tcs.2016.04.014",
language = "English",
volume = "634",
pages = "97--107",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

Structure connectivity and substructure connectivity of hypercubes. / Lin, Cheng Kuan; Zhang, Lili; Fan, Jianxi; Wang, Dajin.

In: Theoretical Computer Science, Vol. 634, 27.06.2016, p. 97-107.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Structure connectivity and substructure connectivity of hypercubes

AU - Lin, Cheng Kuan

AU - Zhang, Lili

AU - Fan, Jianxi

AU - Wang, Dajin

PY - 2016/6/27

Y1 - 2016/6/27

N2 - The connectivity of a network - the minimum number of nodes whose removal will disconnect the network - is directly related to its reliability and fault tolerability, hence an important indicator of the network's robustness. In this paper, we extend the notion of connectivity by introducing two new kinds of connectivity, called structure connectivity and substructure connectivity, respectively. Let H be a certain particular connected subgraph of G. The H-structure connectivity of graph G, denoted κ(G;H), is the cardinality of a minimal set of subgraphs F={H1',H2',. . .,Hm'} in G, such that every Hi'∈F is isomorphic to H, and F's removal will disconnect G. The H-substructure connectivity of graph G, denoted κs(G;H), is the cardinality of a minimal set of subgraphs F={J1, J2, . . ., Jm}, such that every Ji∈F is a connected subgraph of H, and F's removal will disconnect G. In this paper, we will establish both κ(Qn;H) and κs(Qn;H) for the hypercube Qn and H∈{K1, K1,1, K1,2, K1,3, C4}.

AB - The connectivity of a network - the minimum number of nodes whose removal will disconnect the network - is directly related to its reliability and fault tolerability, hence an important indicator of the network's robustness. In this paper, we extend the notion of connectivity by introducing two new kinds of connectivity, called structure connectivity and substructure connectivity, respectively. Let H be a certain particular connected subgraph of G. The H-structure connectivity of graph G, denoted κ(G;H), is the cardinality of a minimal set of subgraphs F={H1',H2',. . .,Hm'} in G, such that every Hi'∈F is isomorphic to H, and F's removal will disconnect G. The H-substructure connectivity of graph G, denoted κs(G;H), is the cardinality of a minimal set of subgraphs F={J1, J2, . . ., Jm}, such that every Ji∈F is a connected subgraph of H, and F's removal will disconnect G. In this paper, we will establish both κ(Qn;H) and κs(Qn;H) for the hypercube Qn and H∈{K1, K1,1, K1,2, K1,3, C4}.

KW - Hypercube

KW - Structure connectivity

KW - Substructure connectivity

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

U2 - 10.1016/j.tcs.2016.04.014

DO - 10.1016/j.tcs.2016.04.014

M3 - Article

AN - SCOPUS:84966714059

VL - 634

SP - 97

EP - 107

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -