R3-connectivity of folded hypercubes

Chia Wei Lee, Sun Yuan Hsieh, Shuen Shiang Yang

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


Given a graph G=(V,E), where V is the node set and E is the edge set of G, and a non-negative integer h, the h-restricted connectivity of G is the minimum size of a set of nodes X of G, where X⊂V(G), such that G[V−X] is disconnected and each node in the remaining graph has at least h neighbors, denoted by κh(G). Folded hypercube FQ is a well-known network topology. An n-dimensional folded hypercube FQn can be obtained from an n-dimensional hypercube by adding a specific perfect matching. In this paper, we show that 3-restricted connectivity of n-dimensional folded hypercube is 8n−16 for n≥6.

Original languageEnglish
Pages (from-to)261-273
Number of pages13
JournalDiscrete Applied Mathematics
Publication statusPublished - 2020 Oct 15

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'R<sub>3</sub>-connectivity of folded hypercubes'. Together they form a unique fingerprint.

Cite this