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 |
Matching, Strong Matching Preclusion, Augmented Butterfly Networks
| [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. |
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
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
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
Share This Article
Twitter
Linked In
Facebook
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}
}
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 -
Email: