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

Research output: Contribution to journalArticle

52 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

All Science Journal Classification (ASJC) codes

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

Cite this