Strong Matching Preclusion for Augmented Butterfly Networks
American Journal of Applied Mathematics
Volume 7, Issue 2, April 2019, Pages: 58-62
Received: May 24, 2019; Accepted: Jun. 27, 2019; Published: Jul. 9, 2019
Views 59      Downloads 34
Authors
Jinyu Zou, School of Computer Sciences, Qinghai Normal University, Xining, China
Yan Sun, School of Computer Sciences, Qinghai Normal University, Xining, China
Chengfu Ye, School of Computer Sciences, Qinghai Normal University, Xining, China
Article Tools
Follow on us
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.
Keywords
Matching, Strong Matching Preclusion, Augmented Butterfly Networks
To cite this article
Jinyu Zou, Yan Sun, Chengfu Ye, Strong Matching Preclusion for Augmented Butterfly Networks, American Journal of Applied Mathematics. Vol. 7, No. 2, 2019, pp. 58-62. doi: 10.11648/j.ajam.20190702.13
Copyright
Copyright © 2019 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
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.
ADDRESS
Science Publishing Group
1 Rockefeller Plaza,
10th and 11th Floors,
New York, NY 10020
U.S.A.
Tel: (001)347-983-5186