MATCHING PRECLUSION AND CONDITIONAL MATCHING PRECLUSION FOR CROSSED CUBES
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. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this paper, we find the matching preclusion number and the conditional matching preclusion number with the classification of the optimal sets for the class of crossed cubes, an important variant of the class of hypercubes. Indeed, we will establish more general results on the matching preclusion and the conditional matching preclusion problems for a larger class of interconnection networks.
References
- J. Inst. Math. Comput. Sci. Comput. Sci. Ser. 18, 17 (2007). ISI, Google Scholar
- Congressus Numerantium 174, 185 (2005). Google Scholar
- International Journal of Foundations of Computer Science 19, 1413 (2008). Link, ISI, Google Scholar
- Information Sciences 179, 1092 (2009). Crossref, ISI, Google Scholar
- Networks 50, 173 (2007). Crossref, ISI, Google Scholar
- E. Cheng, P. Hu, R. Jia, and L. Lipták. Matching preclusion and conditional matching preclusion for bipartite interconnection networks I: sufficient conditions, Networks, to appear . Google Scholar
- E. Cheng, P. Hu, R. Jia, and L. Lipták. Matching preclusion and conditional matching preclusion for bipartite interconnection networks II: Cayley graphs generated by transposition trees and hyper-stars, Networks, to appear . Google Scholar
- International Journal of Computer Mathematics 88, 1120 (2011). Crossref, ISI, Google Scholar
- Information Processing Letters 110, 464 (2010). Crossref, ISI, Google Scholar
- Information Processing Letters 108, 394 (2008). Crossref, ISI, Google Scholar
- Information Sciences 178, 2396 (2008). Crossref, ISI, Google Scholar
- Parallel Computing 20, 1763 (1994). Crossref, ISI, Google Scholar
- Chinese Journal of Computers 21, 456 (1998). Google Scholar
- Information Sciences 176, 3332 (2006). Crossref, ISI, Google Scholar
- Information Processing Letters 93, 133 (2005). Crossref, ISI, Google Scholar
- Journal of Qingdao University Natural Science Edition 15, 19 (2002). ISI, Google Scholar
- Communications and Computer Sciences E 85-A, 1359 (2002). Google Scholar
-
L.-H. Hsu and C.-K. Lin , Graph Theory and Interconnection Networks ( CRC Press , 2009 ) . Google Scholar - Information Sciences 177, 5664 (2007). Crossref, ISI, Google Scholar
- Information Processing Letters 61, 221 (1997). Crossref, ISI, Google Scholar
- Information Sciences 179, 2487 (2009). Crossref, ISI, Google Scholar
- Journal of University of Science and Technology of China 35, 329 (2005). Google Scholar
- Theoretical Computer Science 407, 110 (2008). Crossref, ISI, Google Scholar
- Journal of KIISE 35, 60 (2008). ISI, Google Scholar
- Theoretical Computer Science 410, 2632 (2009). Crossref, ISI, Google Scholar
- Discrete Applied Mathematics 158, 2066 (2010). Crossref, ISI, Google Scholar
- Information Processing Letters 97, 94 (2006). Crossref, ISI, Google Scholar
- Information Processing Letters 88, 149 (2003). Crossref, ISI, Google Scholar
- Information Processing Letters 110, 559 (2010). Crossref, ISI, Google Scholar
- Neural, Parallel, and Scientific Computations 13, 107 (2005). Google Scholar
- Parallel Algorithms Applications 19, 11 (2004). Crossref, Google Scholar
- Chinese Journal of Computers 30, 615 (2007). Google Scholar
- International Journal of Computer Mathematics 87, 3387 (2010). Crossref, ISI, Google Scholar


