Matching preclusion for cube-connected cycles

Qiuli Li, Wai Chee SHIU*, Haiyuan Yao

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

14 Citations (Scopus)
18 Downloads (Pure)


Matching preclusion is a measure of robustness in the event of edge failure in interconnection networks. The matching preclusion number of a graph G with even order is the minimum number of edges whose deletion results in a graph without perfect matchings and the conditional matching preclusion number of G is the minimum number of edges whose deletion leaves the resulting graph with no isolated vertices and without perfect matchings. We consider matching preclusion of cube-connected cycles network CCCn. By using the super-edge-connectivity of vertex-transitive graphs, the super cyclically edge-connectivity of CCCn for n=3,4 and 5, Hall's Theorem and the strengthened Tutte's Theorem, we obtain the matching preclusion number and the conditional matching preclusion number of CCCn and classify respective optimal matching preclusion sets.

Original languageEnglish
Pages (from-to)118-126
Number of pages9
JournalDiscrete Applied Mathematics
Publication statusPublished - 20 Aug 2015

Scopus Subject Areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

User-Defined Keywords

  • Cube-connected cycles
  • Cyclically edge-connectivity
  • Matching preclusion
  • Networks


Dive into the research topics of 'Matching preclusion for cube-connected cycles'. Together they form a unique fingerprint.

Cite this