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.

A Short Note of Strong Matching Preclusion for a Class of Arrangement Graphs

    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. S. B. Akers, D. Harel and B. Krishnamurthy, The star graph: An attractive alternative to the n-cube, in Proc. Int’l Conf. Parallel Processing (1987), pp. 393–400. Google Scholar
    • 2. R. C. Brigham et al., 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. P. Bonneville, E. Cheng and J. Renzi, Strong matching preclusion for the alternating group graphs and split stars, JOIN 12 (2011) 277–298. Google Scholar
    • 5. W. Chang and E. Cheng, Strong matching preclusion of 2-matching composition networks, Congressus Numerantium 224 (2015) 91–104. Google Scholar
    • 6. E. Cheng et al., Matching preclusion for altermating group and their generalizations, Int. J. Found. Comput. Sci. 6 (2008) 1413–1437. LinkGoogle Scholar
    • 7. E. Cheng et al., Conditional matching preclusion for the arrangement graphs, Theor. Comput. Sci. 412 (2011) 6279–6289. Crossref, ISIGoogle Scholar
    • 8. E. Cheng and L. Lipták, Matching preclusion for some interconnection networks, Networks 50 (2007) 173–180. Crossref, ISIGoogle Scholar
    • 9. E. Cheng et al., Conditional matching preclusion sets, Inform. Sci. 179 (2009) 1092–1101. Crossref, ISIGoogle Scholar
    • 10. E. Cheng, R. Jia and D. Lu, Matching preclusion and conditional matching preclusion for augmented cubes, JOIN 11 (2010) 35–60. Google Scholar
    • 11. E. Cheng and O. Siddiqui, Strong matching preclusion of arrangement graphs, JOIN 16 (2016) 1650004. Google Scholar
    • 12. K. Day and A. Tripathi, Arrangement graphs: A class of generalized star graphs, Inform. Proc. Lett. 42 (1992) 235–241. Crossref, ISIGoogle Scholar
    • 13. H.-C. Hsu et al., Fault Hamiltonicity and fault Hamiltonian connectivity of the arrangement graphs, IEEE Trans. Comput. 53 (2004) 39–53. Crossref, ISIGoogle Scholar
    • 14. J.-S. Jwo, S. Lakshmivarahan and S. K. Dhall, A new class of interconnection networks based on the alternating group, Networks 23 (1993) 315–326. Crossref, ISIGoogle Scholar
    • 15. 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
    • 16. Y. Liu and W. Liu, Fractional matching preclusion of graphs, J. Comb. Optim. 34 (2017) 522–533. Crossref, ISIGoogle Scholar
    • 17. T. Ma et al., Fractional matching preclusion for arrangement graphs, Discrete Appl. Math. 270 (2019) 181–189. Crossref, ISIGoogle Scholar
    • 18. Y. Mao et al., Strong matching preclusion number of graphs, Theor. Comput. Sci. 713 (2018) 11–20. Crossref, ISIGoogle Scholar
    • 19. J.-H. Park and I. Ihm, Strong matching preclusion, Theor. Comput. Sci. 412 (2011) 6409–6419. Crossref, ISIGoogle Scholar