A Short Note of Strong Matching Preclusion for a Class of Arrangement Graphs
Abstract
The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. The strong matching preclusion is a well-studied measure for the network invulnerability in the event of edge failure. In this paper, we obtain the strong matching preclusion number for a class of arrangement graphs and categorize their the strong matching preclusion set, which are a supplement of known results.
References
- 1. , The star graph: An attractive alternative to the n-cube, in Proc. Int’l Conf. 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 for the alternating group graphs and split stars, JOIN 12 (2011) 277–298. Google Scholar
- 5. , Strong matching preclusion of 2-matching composition networks, Congressus Numerantium 224 (2015) 91–104. Google Scholar
- 6. , Matching preclusion for altermating group and their generalizations, Int. J. Found. Comput. Sci. 6 (2008) 1413–1437. Link, Google Scholar
- 7. , Conditional matching preclusion for the arrangement graphs, Theor. Comput. Sci. 412 (2011) 6279–6289. Crossref, ISI, Google Scholar
- 8. , Matching preclusion for some interconnection networks, Networks 50 (2007) 173–180. Crossref, ISI, Google Scholar
- 9. , Conditional matching preclusion sets, Inform. Sci. 179 (2009) 1092–1101. Crossref, ISI, Google Scholar
- 10. , Matching preclusion and conditional matching preclusion for augmented cubes, JOIN 11 (2010) 35–60. Google Scholar
- 11. , Strong matching preclusion of arrangement graphs, JOIN 16 (2016) 1650004. Google Scholar
- 12. , Arrangement graphs: A class of generalized star graphs, Inform. Proc. Lett. 42 (1992) 235–241. Crossref, ISI, Google Scholar
- 13. , Fault Hamiltonicity and fault Hamiltonian connectivity of the arrangement graphs, IEEE Trans. Comput. 53 (2004) 39–53. Crossref, ISI, Google Scholar
- 14. , A new class of interconnection networks based on the alternating group, Networks 23 (1993) 315–326. Crossref, ISI, Google Scholar
- 15. , Matching preclusion for vertex-transitive networks, Discrete Appl. Math. 207 (2016) 90–98. Crossref, ISI, Google Scholar
- 16. , Fractional matching preclusion of graphs, J. Comb. Optim. 34 (2017) 522–533. Crossref, ISI, Google Scholar
- 17. , Fractional matching preclusion for arrangement graphs, Discrete Appl. Math. 270 (2019) 181–189. Crossref, ISI, Google Scholar
- 18. , Strong matching preclusion number of graphs, Theor. Comput. Sci. 713 (2018) 11–20. Crossref, ISI, Google Scholar
- 19. , Strong matching preclusion, Theor. Comput. Sci. 412 (2011) 6409–6419. Crossref, ISI, Google Scholar


