| Peer-Reviewed

Strong Matching Preclusion for Augmented Butterfly Networks

Received: 24 May 2019     Accepted: 27 June 2019     Published: 9 July 2019
Views:       Downloads:
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. The strong matching preclusion number (or simply, SMP number) smp(G) of a graph G is the minimum number of vertices and/or edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. This is an extension of the matching preclusion problem and has been introduced by Park and Ihm. Butterfly Networks are interconnection networks which form the back bone of distributed memory parallel architecture. One of the current interests of researchers is Butterfly graphs, because they are studied as a topology of parallel machine architecture. Butterfly network has many weaknesses. It is non-Hamiltonian, not pancyclic and its toughness is less than one. But augmented butterfly network retains most of the favorable properties of the butterfly network. In this paper, we determine the strong matching preclusion number of the Augmented Butterfly networks.

Published in American Journal of Applied Mathematics (Volume 7, Issue 2)
DOI 10.11648/j.ajam.20190702.13
Page(s) 58-62
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2019. Published by Science Publishing Group

Keywords

Matching, Strong Matching Preclusion, Augmented Butterfly Networks

References
[1] P. Bonnevilie, E. Cheng, J. Renzi, strong matching preclusion for the alternating group graphs and split-stars, J. Interconnection. Netw., 2011, Vol. 12, No. 4, 277-298.
[2] R. C. Brigham, F. Harary, E. C. Violin, J. Yellen, perfect matching preclusion, Congr. Numer 2005, 185-192.
[3] J. Bondy, U. Murty, Graph Theory, GTM244, Springer, 2008.
[4] P. Manuel, I. Rajasingh, B. Rajan and Prabha, Augmented Butterfly Network, J. Combin. Inform. Syst. Sci. 2008, 33, 27-35.
[5] M. J. Raja, D. A. Xavier. Conditional Matching Preclusion Number for Butterfly Derived Networks. Inter. J. Pure Appl. Math. 2016, 7, 17-25.
[6] J.-H. Park, Matching preclusion problem in restricted HL-graphs and recursive circulate g(2m, 4), Journal of KIISE 2008, 35, 60-65.
[7] J.-H. Park, I. Ihm, Strong matching preclusion, Theor. Comput. Sci. 2011, 412, 6409-6419.
[8] J.-H. Park, I. Ihm, Strong matching preclusion under the conditional fault model, Discrete Appl. Math 2013, 161, 1093-1105.
[9] E. Cheng, J. Kelm, J. Renzi, Strong matching preclusion of (n, k)-star graphs, Theory. Comput. Sci. 2016, 615, 91--101.
[10] E. Cheng, D. Lu, B. Xu, Strong matching preclusion of pancake graphs, J. Interconnection. Netw 2013, 14 (2), 1350007.
[11] E. Cheng, S. Shah, V. Shah, D. E. Steffy, Strong matching preclusion for augmented cubes, Theor. Comput. Sci. 2013, 491, 71-77.
[12] S. Wang, K. Feng, G. Zhang, Strong matching preclusion for k-ary n-cubes, Discrete Appl. Math 2013, 161, 3054-3062.
[13] X. M. Hu, Y. Z. Tian, X. D. Liang, J. X. Meng, Strong matching preclusion for n-dimensional torus networks, Theor. Comput. Sci 2016, 635, 64-73.
[14] X. M. Hu, Y. Z. Tian, X. D. Liang, J. X. Meng, Strong matching preclusion for k-composition networks, Theor. Comput. Sci 2018, 711, 36-43.
[15] Y. Mao, Z. Wang, E. Cheng, C. Melekian, Strong matching preclusionnumber of graphs, Theor. Comput. Sci. 2018, 713, 11-20.
[16] Z. Wang, Y. Mao, E. Cheng, J. Y. Zou, Matching preclusion number of graphs, Theor. Comput. Sci 2019, 759, 61-71.
Cite This Article
  • APA Style

    Jinyu Zou, Yan Sun, Chengfu Ye. (2019). Strong Matching Preclusion for Augmented Butterfly Networks. American Journal of Applied Mathematics, 7(2), 58-62. https://doi.org/10.11648/j.ajam.20190702.13

    Copy | Download

    ACS Style

    Jinyu Zou; Yan Sun; Chengfu Ye. Strong Matching Preclusion for Augmented Butterfly Networks. Am. J. Appl. Math. 2019, 7(2), 58-62. doi: 10.11648/j.ajam.20190702.13

    Copy | Download

    AMA Style

    Jinyu Zou, Yan Sun, Chengfu Ye. Strong Matching Preclusion for Augmented Butterfly Networks. Am J Appl Math. 2019;7(2):58-62. doi: 10.11648/j.ajam.20190702.13

    Copy | Download

  • @article{10.11648/j.ajam.20190702.13,
      author = {Jinyu Zou and Yan Sun and Chengfu Ye},
      title = {Strong Matching Preclusion for Augmented Butterfly Networks},
      journal = {American Journal of Applied Mathematics},
      volume = {7},
      number = {2},
      pages = {58-62},
      doi = {10.11648/j.ajam.20190702.13},
      url = {https://doi.org/10.11648/j.ajam.20190702.13},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajam.20190702.13},
      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. The strong matching preclusion number (or simply, SMP number) smp(G) of a graph G is the minimum number of vertices and/or edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. This is an extension of the matching preclusion problem and has been introduced by Park and Ihm. Butterfly Networks are interconnection networks which form the back bone of distributed memory parallel architecture. One of the current interests of researchers is Butterfly graphs, because they are studied as a topology of parallel machine architecture. Butterfly network has many weaknesses. It is non-Hamiltonian, not pancyclic and its toughness is less than one. But augmented butterfly network retains most of the favorable properties of the butterfly network. In this paper, we determine the strong matching preclusion number of the Augmented Butterfly networks.},
     year = {2019}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Strong Matching Preclusion for Augmented Butterfly Networks
    AU  - Jinyu Zou
    AU  - Yan Sun
    AU  - Chengfu Ye
    Y1  - 2019/07/09
    PY  - 2019
    N1  - https://doi.org/10.11648/j.ajam.20190702.13
    DO  - 10.11648/j.ajam.20190702.13
    T2  - American Journal of Applied Mathematics
    JF  - American Journal of Applied Mathematics
    JO  - American Journal of Applied Mathematics
    SP  - 58
    EP  - 62
    PB  - Science Publishing Group
    SN  - 2330-006X
    UR  - https://doi.org/10.11648/j.ajam.20190702.13
    AB  - 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. The strong matching preclusion number (or simply, SMP number) smp(G) of a graph G is the minimum number of vertices and/or edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. This is an extension of the matching preclusion problem and has been introduced by Park and Ihm. Butterfly Networks are interconnection networks which form the back bone of distributed memory parallel architecture. One of the current interests of researchers is Butterfly graphs, because they are studied as a topology of parallel machine architecture. Butterfly network has many weaknesses. It is non-Hamiltonian, not pancyclic and its toughness is less than one. But augmented butterfly network retains most of the favorable properties of the butterfly network. In this paper, we determine the strong matching preclusion number of the Augmented Butterfly networks.
    VL  - 7
    IS  - 2
    ER  - 

    Copy | Download

Author Information
  • School of Computer Sciences, Qinghai Normal University, Xining, China

  • School of Computer Sciences, Qinghai Normal University, Xining, China

  • School of Computer Sciences, Qinghai Normal University, Xining, China

  • Sections