Abstract
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 language | English (US) |
|---|---|
| Pages (from-to) | 2408-2418 |
| Number of pages | 11 |
| Journal | International Journal of Computer Mathematics |
| Volume | 87 |
| Issue number | 11 |
| DOIs | |
| State | Published - Sep 2010 |
| Externally published | Yes |
Keywords
- (n, k)-bubble-sort graphs
- Cayley graphs
- Hamiltonian
- interconnection networks
- perfect matching