World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

MATCHING PRECLUSION AND CONDITIONAL MATCHING PRECLUSION FOR CROSSED CUBES

    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

    • E. Abuelrub, J. Inst. Math. Comput. Sci. Comput. Sci. Ser. 18, 17 (2007). ISIGoogle Scholar
    • R. C. Brighamet al., Congressus Numerantium 174, 185 (2005). Google Scholar
    • E. Chenget al., International Journal of Foundations of Computer Science 19, 1413 (2008). Link, ISIGoogle Scholar
    • E. Chenget al., Information Sciences 179, 1092 (2009). Crossref, ISIGoogle Scholar
    • E. Cheng and L. Lipták, Networks 50, 173 (2007). Crossref, ISIGoogle 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
    • E. Chenget al., International Journal of Computer Mathematics 88, 1120 (2011). Crossref, ISIGoogle Scholar
    • Q. Dong and X. Yang, Information Processing Letters 110, 464 (2010). Crossref, ISIGoogle Scholar
    • Q. Dong, X. Yang and J. Zhao, Information Processing Letters 108, 394 (2008). Crossref, ISIGoogle Scholar
    • Q. Donget al., Information Sciences 178, 2396 (2008). Crossref, ISIGoogle Scholar
    • K. Efeet al., Parallel Computing 20, 1763 (1994). Crossref, ISIGoogle Scholar
    • J. X. Fan, Chinese Journal of Computers 21, 456 (1998). Google Scholar
    • J. Fan, X. Jia and X. Lin, Information Sciences 176, 3332 (2006). Crossref, ISIGoogle Scholar
    • J. Fan, X. Lin and X. Jia, Information Processing Letters 93, 133 (2005). Crossref, ISIGoogle Scholar
    • J.-X. Fanet al., Journal of Qingdao University Natural Science Edition 15, 19 (2002). ISIGoogle Scholar
    • W.-T. Huanget al., 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
    • H.-S. Hung, J.-S. Fu and G.-H. Cheng, Information Sciences 177, 5664 (2007). Crossref, ISIGoogle Scholar
    • P. D. Kulasinghe, Information Processing Letters 61, 221 (1997). Crossref, ISIGoogle Scholar
    • P.-L. Lai and H.-C. Hsu, Information Sciences 179, 2487 (2009). Crossref, ISIGoogle Scholar
    • M. Ma and J.-M. Xu, Journal of University of Science and Technology of China 35, 329 (2005). Google Scholar
    • M. Ma, G. Liu and J.-M. Xu, Theoretical Computer Science 407, 110 (2008). Crossref, ISIGoogle Scholar
    • J.-H. Park, Journal of KIISE 35, 60 (2008). ISIGoogle Scholar
    • J.-H. Park and S. H. Son, Theoretical Computer Science 410, 2632 (2009). Crossref, ISIGoogle Scholar
    • S. Wanget al., Discrete Applied Mathematics 158, 2066 (2010). Crossref, ISIGoogle Scholar
    • J.-M. Xu, M. Ma and M. Lü, Information Processing Letters 97, 94 (2006). Crossref, ISIGoogle Scholar
    • M.-C. Yanget al., Information Processing Letters 88, 149 (2003). Crossref, ISIGoogle Scholar
    • X. Yang, Q. Dong and Y. Y. Tang, Information Processing Letters 110, 559 (2010). Crossref, ISIGoogle Scholar
    • X. Yanget al., Neural, Parallel, and Scientific Computations 13, 107 (2005). Google Scholar
    • X. Yang and G. M. Megson, Parallel Algorithms Applications 19, 11 (2004). CrossrefGoogle Scholar
    • X. Yu, M. Wu and G. J. Wang, Chinese Journal of Computers 30, 615 (2007). Google Scholar
    • S. Zhou, International Journal of Computer Mathematics 87, 3387 (2010). Crossref, ISIGoogle Scholar