Matching preclusion for the (n, k)-bubble-sort graphs

Eddie Cheng, Laszló Láiptak, David Sherman

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. In this paper, we find this number for the (n, k)-bubble-sort graphs and classify all the optimal solutions.

Original languageEnglish (US)
Pages (from-to)2408-2418
Number of pages11
JournalInternational Journal of Computer Mathematics
Issue number11
StatePublished - Sep 1 2010


  • (n, k)-bubble-sort graphs
  • Cayley graphs
  • Hamiltonian
  • interconnection networks
  • perfect matching

Fingerprint Dive into the research topics of 'Matching preclusion for the (n, k)-bubble-sort graphs'. Together they form a unique fingerprint.

Cite this