On 3-extra connectivity and 3-extra edge connectivity of folded hypercubes

Nai Wen Chang, Cheng Yen Tsai, Sun Yuan Hsieh

Research output: Contribution to journalArticlepeer-review

67 Citations (Scopus)


Given a graph G and a non-negative integer g , the g-extra connectivity (resp. g-extra edge connectivity) of G is the minimum cardinality of a set of vertices (resp. edges) in G , if it exists, whose deletion disconnects G and leaves each remaining component with more than g vertices. This study shows that the 3-extra connectivity (resp. 3-extra edge connectivity) of an n-dimensional folded hypercube is 4 n-5 for n ≥ 6 (resp. 4 n-4 for n ≥ 5). This study also provides an upper bound for the g-extra connectivity on folded hypercubes for g ≥ 6.

Original languageEnglish
Article number6409834
Pages (from-to)1594-1600
Number of pages7
JournalIEEE Transactions on Computers
Issue number6
Publication statusPublished - 2014 Jun

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On 3-extra connectivity and 3-extra edge connectivity of folded hypercubes'. Together they form a unique fingerprint.

Cite this