{2, 3} -Extraconnectivities of hypercube-like networks

Research output: Contribution to journalArticle

48 Citations (Scopus)

Abstract

A subset of vertices X is said to be a cutset if G-X is not connected. A cutset X is called an Rg-cutset if every component of G-X has at least g+1 vertices. If G has at least one Rg-cutset, the g-extraconnectivity of G is then defined as the minimum cardinality over all Rg-cutsets of G. In this paper, we first show that the 2-extraconnectivity of an n-dimensional hypercube-like network is 3n-5 for n≥5. This improves on the previously best known result, which showed that the 2-extraconnectivity of an n-dimensional hypercube-like network is 3n-5 for n≥8. We further demonstrate that the 3-extraconnectivity of an n-dimensional hypercube-like network is 4n-9 for n≥6. Based on the above results, the 2-extraconnectivity and 3-extraconnectivity of several interconnection networks, including hypercubes, twisted cubes, crossed cubes, Möbius cubes, locally twisted cubes, generalized twisted cubes, recursive circulants, and Mcubes, can be determined efficiently.

Original languageEnglish
Pages (from-to)669-688
Number of pages20
JournalJournal of Computer and System Sciences
Volume79
Issue number5
DOIs
Publication statusPublished - 2013 Aug 1

Fingerprint

Cutset
Hypercube
Regular hexahedron
n-dimensional
Crossed Cube
Interconnection Networks
Cardinality
Subset
Demonstrate

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this

@article{675bb4a51ba34cc09a9cee5e09dbf02d,
title = "{2, 3} -Extraconnectivities of hypercube-like networks",
abstract = "A subset of vertices X is said to be a cutset if G-X is not connected. A cutset X is called an Rg-cutset if every component of G-X has at least g+1 vertices. If G has at least one Rg-cutset, the g-extraconnectivity of G is then defined as the minimum cardinality over all Rg-cutsets of G. In this paper, we first show that the 2-extraconnectivity of an n-dimensional hypercube-like network is 3n-5 for n≥5. This improves on the previously best known result, which showed that the 2-extraconnectivity of an n-dimensional hypercube-like network is 3n-5 for n≥8. We further demonstrate that the 3-extraconnectivity of an n-dimensional hypercube-like network is 4n-9 for n≥6. Based on the above results, the 2-extraconnectivity and 3-extraconnectivity of several interconnection networks, including hypercubes, twisted cubes, crossed cubes, M{\"o}bius cubes, locally twisted cubes, generalized twisted cubes, recursive circulants, and Mcubes, can be determined efficiently.",
author = "Chang, {Nai Wen} and Hsieh, {Sun Yuan}",
year = "2013",
month = "8",
day = "1",
doi = "10.1016/j.jcss.2013.01.013",
language = "English",
volume = "79",
pages = "669--688",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Academic Press Inc.",
number = "5",

}

{2, 3} -Extraconnectivities of hypercube-like networks. / Chang, Nai Wen; Hsieh, Sun Yuan.

In: Journal of Computer and System Sciences, Vol. 79, No. 5, 01.08.2013, p. 669-688.

Research output: Contribution to journalArticle

TY - JOUR

T1 - {2, 3} -Extraconnectivities of hypercube-like networks

AU - Chang, Nai Wen

AU - Hsieh, Sun Yuan

PY - 2013/8/1

Y1 - 2013/8/1

N2 - A subset of vertices X is said to be a cutset if G-X is not connected. A cutset X is called an Rg-cutset if every component of G-X has at least g+1 vertices. If G has at least one Rg-cutset, the g-extraconnectivity of G is then defined as the minimum cardinality over all Rg-cutsets of G. In this paper, we first show that the 2-extraconnectivity of an n-dimensional hypercube-like network is 3n-5 for n≥5. This improves on the previously best known result, which showed that the 2-extraconnectivity of an n-dimensional hypercube-like network is 3n-5 for n≥8. We further demonstrate that the 3-extraconnectivity of an n-dimensional hypercube-like network is 4n-9 for n≥6. Based on the above results, the 2-extraconnectivity and 3-extraconnectivity of several interconnection networks, including hypercubes, twisted cubes, crossed cubes, Möbius cubes, locally twisted cubes, generalized twisted cubes, recursive circulants, and Mcubes, can be determined efficiently.

AB - A subset of vertices X is said to be a cutset if G-X is not connected. A cutset X is called an Rg-cutset if every component of G-X has at least g+1 vertices. If G has at least one Rg-cutset, the g-extraconnectivity of G is then defined as the minimum cardinality over all Rg-cutsets of G. In this paper, we first show that the 2-extraconnectivity of an n-dimensional hypercube-like network is 3n-5 for n≥5. This improves on the previously best known result, which showed that the 2-extraconnectivity of an n-dimensional hypercube-like network is 3n-5 for n≥8. We further demonstrate that the 3-extraconnectivity of an n-dimensional hypercube-like network is 4n-9 for n≥6. Based on the above results, the 2-extraconnectivity and 3-extraconnectivity of several interconnection networks, including hypercubes, twisted cubes, crossed cubes, Möbius cubes, locally twisted cubes, generalized twisted cubes, recursive circulants, and Mcubes, can be determined efficiently.

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

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

U2 - 10.1016/j.jcss.2013.01.013

DO - 10.1016/j.jcss.2013.01.013

M3 - Article

AN - SCOPUS:84875232028

VL - 79

SP - 669

EP - 688

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 5

ER -