Fractional Matching Preclusion for (n, k)-Star Graphs
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. 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. , The star graph: An attractive alternative to the n-cube, in Proc. Int. Conf. on Parallel Processing (
1987 ), pp. 393–400. Google Scholar - 2. , Perfect-matching preclusion, Congressus Numerantium 174 (2005) 185–192. Google Scholar
- 3. , Graph Theory (GTM244) (Springer, 2008). Crossref, Google Scholar
- 4. , Strong matching preclusion of 2-matching composition networks, Congressus Numerantium 224 (2015) 91–104. Google Scholar
- 5. , Strong matching preclusion of (n, k)-star graphs, Theor. Comput. Sci. 615 (2016) 91–101. Crossref, ISI, Google Scholar
- 6. , Conditional matching preclusion for (n, k)-star graphs, Parall. Process. Lett. 23 (2013) 1350004. Link, Google Scholar
- 7. , Matching preclusion for some interconnection networks, Networks 50 (2007) 173–180. Crossref, ISI, Google Scholar
- 8. , Conditional matching preclusion sets, Inform. Sci. 179 (2009) 1092–1101. Crossref, ISI, Google Scholar
- 9. , Strong matching preclusion for augmented cubes, Theor. Comput. Sci. 491 (2013) 71–77. Crossref, ISI, Google Scholar
- 10. , The (n, k)-star graph: A generalized star graph, Inform. Process. Lett. 56 (1995) 259–264. Crossref, ISI, Google Scholar
- 11. , Fault Hamiltonicity and fault Hamiltonian connectivity of the (n, k)-star graphs, Networks 42 (2003) 189–201. Crossref, ISI, Google Scholar
- 12. , Matching preclusion for vertex-transitive networks, Discrete Appl. Math. 207 (2016) 90–98. Crossref, ISI, Google Scholar
- 13. , The generalized 3-connectivity of star graphs and bubble-sort graphs, Appl. Math. Comput. 274 (2016) 41–46. Google Scholar
- 14. , Fractional matching preclusion of graphs, J. Comb. Optim. 34 (2017) 522–533. Crossref, ISI, Google Scholar
- 15. , Strong matching preclusion number of graphs, Theor. Comput. Sci. 713 (2018) 11–20. Crossref, ISI, Google Scholar
- 16. , Strong matching preclusion, Theor. Comput. Sci. 412 (2011) 6409–6419. Crossref, ISI, Google Scholar
- 17. , Fractional Graph Theory: A Rational Approach to the Theory of Graphs (John Wiley, New York, 1997). Google Scholar
- 18. , The factorization of linear graphs, J. London Math. Soc. 22 (1947) 107–111. Crossref, Google 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. , A kind of conditional fault tolerance of (n, k)-star graphs, Inform. Process. Lett. 110 (2010) 1007–1011. Crossref, ISI, Google Scholar
- 21. , The conditional fault diagnosability of (n, k)-star graphs, Appl. Math. Comput. 218 (2012) 9742–9749. Crossref, ISI, Google Scholar


