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 Matching Preclusion for (n, k)-Star Graphs

    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. As a generalization, Liu and Liu introduced the concept of fractional matching preclusion number in 2017. The Fractional Matching Preclusion Number (FMP number) of G is the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The Fractional Strong Matching Preclusion Number (FSMP number) of G is the minimum number of vertices and/or edges whose deletion leaves the resulting graph without a fractional perfect matching. In this paper, we obtain the FMP number and the FSMP number for (n, k)-star graphs. In addition, all the optimal fractional strong matching preclusion sets of these graphs are categorized.

    References

    • 1. S. B. Akers, D. Harel and B. Krishnamurthy, The star graph: An attractive alternative to the n-cube, in Proc. Int. Conf. on Parallel Processing (1987), pp. 393–400. Google Scholar
    • 2. R. C. Brigham, F. Harary and E. C. Violin and J. Yellen, Perfect-matching preclusion, Congressus Numerantium 174 (2005) 185–192. Google Scholar
    • 3. J. A. Bondy and U. S. R. Murty, Graph Theory (GTM244) (Springer, 2008). CrossrefGoogle Scholar
    • 4. W. Chang and E. Cheng, Strong matching preclusion of 2-matching composition networks, Congressus Numerantium 224 (2015) 91–104. Google Scholar
    • 5. E. Cheng, J. Kelm and J. Renzi, Strong matching preclusion of (n, k)-star graphs, Theor. Comput. Sci. 615 (2016) 91–101. Crossref, ISIGoogle Scholar
    • 6. E. Cheng and L. Lipták, Conditional matching preclusion for (n, k)-star graphs, Parall. Process. Lett. 23 (2013) 1350004. LinkGoogle Scholar
    • 7. E. Cheng and L. Lipták, Matching preclusion for some interconnection networks, Networks 50 (2007) 173–180. Crossref, ISIGoogle Scholar
    • 8. E. Cheng, L. Lesniak, M. J. Lipman and L. Lipták, Conditional matching preclusion sets, Inform. Sci. 179 (2009) 1092–1101. Crossref, ISIGoogle Scholar
    • 9. E. Cheng, S. Shah, V. Shah and D. E. Steffy, Strong matching preclusion for augmented cubes, Theor. Comput. Sci. 491 (2013) 71–77. Crossref, ISIGoogle Scholar
    • 10. W.-K. Chiang and R.-J. Chen, The (n, k)-star graph: A generalized star graph, Inform. Process. Lett. 56 (1995) 259–264. Crossref, ISIGoogle Scholar
    • 11. H.-C. Hsu, Y.-L. Hsieh, J. J. M. Tan and L. H. Hsu, Fault Hamiltonicity and fault Hamiltonian connectivity of the (n, k)-star graphs, Networks 42 (2003) 189–201. Crossref, ISIGoogle Scholar
    • 12. Q. L. Li, J. H. He and H. P. Zhang, Matching preclusion for vertex-transitive networks, Discrete Appl. Math. 207 (2016) 90–98. Crossref, ISIGoogle Scholar
    • 13. S. S. Li, J. H. Tu and C. Y. Yu, The generalized 3-connectivity of star graphs and bubble-sort graphs, Appl. Math. Comput. 274 (2016) 41–46. Google Scholar
    • 14. Y. Liu and W. Liu, Fractional matching preclusion of graphs, J. Comb. Optim. 34 (2017) 522–533. Crossref, ISIGoogle Scholar
    • 15. Y. Mao, Z. Wang, E. Cheng and C. Melekian, Strong matching preclusion number of graphs, Theor. Comput. Sci. 713 (2018) 11–20. Crossref, ISIGoogle Scholar
    • 16. J.-H. Park and I. Ihm, Strong matching preclusion, Theor. Comput. Sci. 412 (2011) 6409–6419. Crossref, ISIGoogle Scholar
    • 17. E. R. Scheinerman and D. H. Ullman, Fractional Graph Theory: A Rational Approach to the Theory of Graphs (John Wiley, New York, 1997). Google Scholar
    • 18. W. T. Tutte, The factorization of linear graphs, J. London Math. Soc. 22 (1947) 107–111. CrossrefGoogle Scholar
    • 19. Z. Wang, C. Melekian, E. Cheng and Y. Mao, Matching preclusion number in product graphs, Theor. Comput. Sci., in press. Google Scholar
    • 20. W. H. Yang, H. Z. Li and X. F. Guo, A kind of conditional fault tolerance of (n, k)-star graphs, Inform. Process. Lett. 110 (2010) 1007–1011. Crossref, ISIGoogle Scholar
    • 21. S. Zhou, The conditional fault diagnosability of (n, k)-star graphs, Appl. Math. Comput. 218 (2012) 9742–9749. Crossref, ISIGoogle Scholar