{2,3}- Restricted connectivity of locally twisted cubes

Sun-Yuan Hsieh, Hong Wen Huang, Chia Wei Lee

Research output: Contribution to journalArticle

14 Citations (Scopus)

Abstract

Given a graph G and non-negative integer h, the h-restricted connectivity of G is the minimum cardinality of a set of nodes in G, if exists, whose deletion disconnects G and the degree of each node in every remaining component is at least h. The h-restricted connectivity is a generalization of the classical connectivity and can provide more accurate measures for the reliability or fault-tolerance of multiprocessor system. The n-dimensional locally twisted cubes, denoted by LTQn, are a well-known network topology for building multiprocessor systems. In this paper, we first show that 2-restricted connectivity of the n-dimensional locally twisted cubes is 4n-8 for n≥4, and show that 3-restricted connectivity is equal to 8n-24 for n≥5.

Original languageEnglish
Pages (from-to)78-90
Number of pages13
JournalTheoretical Computer Science
Volume615
DOIs
Publication statusPublished - 2016 Feb 15

Fingerprint

Fault tolerance
Regular hexahedron
Connectivity
Topology
Multiprocessor Systems
n-dimensional
Vertex of a graph
Fault Tolerance
Network Topology
Deletion
Cardinality
Non-negative
Integer
Graph in graph theory

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Hsieh, Sun-Yuan ; Huang, Hong Wen ; Lee, Chia Wei. / {2,3}- Restricted connectivity of locally twisted cubes. In: Theoretical Computer Science. 2016 ; Vol. 615. pp. 78-90.
@article{83b769a866ed4fd08f695f32e218015d,
title = "{2,3}- Restricted connectivity of locally twisted cubes",
abstract = "Given a graph G and non-negative integer h, the h-restricted connectivity of G is the minimum cardinality of a set of nodes in G, if exists, whose deletion disconnects G and the degree of each node in every remaining component is at least h. The h-restricted connectivity is a generalization of the classical connectivity and can provide more accurate measures for the reliability or fault-tolerance of multiprocessor system. The n-dimensional locally twisted cubes, denoted by LTQn, are a well-known network topology for building multiprocessor systems. In this paper, we first show that 2-restricted connectivity of the n-dimensional locally twisted cubes is 4n-8 for n≥4, and show that 3-restricted connectivity is equal to 8n-24 for n≥5.",
author = "Sun-Yuan Hsieh and Huang, {Hong Wen} and Lee, {Chia Wei}",
year = "2016",
month = "2",
day = "15",
doi = "10.1016/j.tcs.2015.11.050",
language = "English",
volume = "615",
pages = "78--90",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

{2,3}- Restricted connectivity of locally twisted cubes. / Hsieh, Sun-Yuan; Huang, Hong Wen; Lee, Chia Wei.

In: Theoretical Computer Science, Vol. 615, 15.02.2016, p. 78-90.

Research output: Contribution to journalArticle

TY - JOUR

T1 - {2,3}- Restricted connectivity of locally twisted cubes

AU - Hsieh, Sun-Yuan

AU - Huang, Hong Wen

AU - Lee, Chia Wei

PY - 2016/2/15

Y1 - 2016/2/15

N2 - Given a graph G and non-negative integer h, the h-restricted connectivity of G is the minimum cardinality of a set of nodes in G, if exists, whose deletion disconnects G and the degree of each node in every remaining component is at least h. The h-restricted connectivity is a generalization of the classical connectivity and can provide more accurate measures for the reliability or fault-tolerance of multiprocessor system. The n-dimensional locally twisted cubes, denoted by LTQn, are a well-known network topology for building multiprocessor systems. In this paper, we first show that 2-restricted connectivity of the n-dimensional locally twisted cubes is 4n-8 for n≥4, and show that 3-restricted connectivity is equal to 8n-24 for n≥5.

AB - Given a graph G and non-negative integer h, the h-restricted connectivity of G is the minimum cardinality of a set of nodes in G, if exists, whose deletion disconnects G and the degree of each node in every remaining component is at least h. The h-restricted connectivity is a generalization of the classical connectivity and can provide more accurate measures for the reliability or fault-tolerance of multiprocessor system. The n-dimensional locally twisted cubes, denoted by LTQn, are a well-known network topology for building multiprocessor systems. In this paper, we first show that 2-restricted connectivity of the n-dimensional locally twisted cubes is 4n-8 for n≥4, and show that 3-restricted connectivity is equal to 8n-24 for n≥5.

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

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

U2 - 10.1016/j.tcs.2015.11.050

DO - 10.1016/j.tcs.2015.11.050

M3 - Article

AN - SCOPUS:84953369570

VL - 615

SP - 78

EP - 90

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -