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.

Fractional Strong Matching Preclusion for DHcube

    Let F be a set edges and F be a set of edges and/or vertices of a graph G, then F (resp. F) is a fractional matching preclusion set (resp. fractional strong matching preclusion set) if GF (resp. GF) contains no fractional perfect matching. The fractional matching preclusion number (resp. fractional strong matching preclusion number) of G is the minimum size of fractional matching preclusion set (resp. fractional strong matching preclusion set) of G. In this paper, we obtain the fractional matching preclusion number and fractional strong matching preclusion number of the DHcube DH(m,d,n) for n3. In addition, all the optimal fractional matching preclusion sets and fractional strong matching preclusion sets of these graphs are categorized.

    PACS: AMS Subject Classification 2010: 05C05, 05C12, 05C76

    References

    • 1. R. C. Birgham, F. Harry, E. C. Biolin, J. Yellen, Perfect matching preclusion, Congressus Numerantium 174 (2005) 185–192. Google Scholar
    • 2. E. Cheng, L. Lipták, Matching preclusion for some interconnection networks, Networks 50 (2007) 173–180. Crossref, ISIGoogle Scholar
    • 3. E. Cheng, L. Lensik, M. Lipman, L. Lipták, Matching preclusion for alternating group graphs and their generalizations, Int. J. Found. Comp. Sci. 19 (2008) 1413–1437. Link, ISIGoogle Scholar
    • 4. E. Cheng, L. Lensik, M. Lipman, L. Lipták, Conditional Matching preclusion sets, Inf. Sci. 179 (2009) 1092–1101. Crossref, ISIGoogle Scholar
    • 5. T. Ma, Y. Mao, E. Cheng, J. Wang, Fractional matching preclusion for (n, k)-star graphs, Parall. Process. Lett. 28 (2018) 1850017. Link, ISIGoogle Scholar
    • 6. H. Lv, X. Li, H. Zhang, Matching preclusion for balanced hypercubes, Theor. Comput. Sci. 465 (2012) 10–20. Crossref, ISIGoogle Scholar
    • 7. J.-S. Hwo, S. Lakshmivarahan, S. K. Dhall, A new class of interconnection networks based on the alternating group, Networks 23 (1993) 315–326. Crossref, ISIGoogle Scholar
    • 8. J.-H. Park, I. Ihm, Strong matching preclusion, Theor. Comput. Sci. 412 (2011) 6409–6419. Crossref, ISIGoogle Scholar
    • 9. Y. Liu, W. Liu, Fractional matching preclusion of graphs, J. Comb. Optim. 34 (2016) 522–533. Crossref, ISIGoogle Scholar
    • 10. T. Ma, Y. Mao, E. Cheng, C. Melekian, Fractional matching preclusion for (burnt) pancake graphs, International Symposium on Pervasive Systems, Algorithms and Networks, 2018. Google Scholar
    • 11. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (United States of America, 1979). Google Scholar
    • 12. D. S. Johnson, The NP-completeness column: An ongoing guide, J. Algorithms 9 (1982) 426–444. Crossref, ISIGoogle Scholar
    • 13. R. W. Hung, DVcube: A novel compound architecture of disc-ring graph and hypercube-like graph, Theor. Comput. Sci. 498 (2013) 28–45. Crossref, ISIGoogle Scholar
    • 14. A. S. Vaidya, P. S. N. Rao, S. R. Shankar, A class of hypercube-like networks, in Proc. of the 5th IEEE Symposium on Parallel and Distributed Processing (SPDP), 1993, pp. 800–803. Google Scholar
    • 15. T. Ma, Y. Mao, E. Cheng, J. Wang, Fractional matching preclusion for arrangement graphs, Discrete Appl. Math. 270 (2019) 181–189. Crossref, ISIGoogle Scholar
    • 16. K. Efe, The crossed cube architecture for parallel computing, IEEE Trans. Parallel Distrib. Syst. 3 (1992) 513–524. Crossref, ISIGoogle Scholar
    • 17. P. A. J. Hilbers, M. R. J. Koopman, J. L. A. van de Snepscheut, The twisted cube, PARLE: Parallel Architectures and Languages Europe, Volume 1: Parallel Architectures (1987), pp. 152–159. CrossrefGoogle Scholar
    • 18. K. Efe, A variation on the hypercube with lower diameter, IEEE Trans. Comput. 40 (1991) 1312–1316. Crossref, ISIGoogle Scholar
    • 19. P. Cull, S. Larson, The Möbius cubes, IEEE Trans. Comput. 44 (1995) 647–659. Crossref, ISIGoogle Scholar
    • 20. N. K. Singhvi, K. Ghose, The Mcube: A symmetrical cube based network with twisted links, in Proc. of the 9th IEEE International Parallel Processing Symposium (IPPS), 1995, pp. 11–16. Google Scholar
    • 21. D. Guo, H. Chen, Y. He, H. Jin, C. Chen, H. Chen, Z. Shu, G. Huang, KCube: A novel architecture for interconnection networks, Inform. Process. Lett. 110 (2010) 821–825. Crossref, ISIGoogle Scholar
    • 22. X. Qin, R. Hao, Hamiltonian properties of some compound networks, Discrete Appl. Math. 239 (2018) 174–182. Crossref, ISIGoogle Scholar