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 92 Downloads 43
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
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.
Strong Matching Preclusion for Augmented Butterfly Networks, American Journal of Applied Mathematics.
Vol. 7, No. 2,
2019, pp. 58-62.
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.
R. C. Brigham, F. Harary, E. C. Violin, J. Yellen, perfect matching preclusion, Congr. Numer 2005, 185-192.
J. Bondy, U. Murty, Graph Theory, GTM244, Springer, 2008.
P. Manuel, I. Rajasingh, B. Rajan and Prabha, Augmented Butterfly Network, J. Combin. Inform. Syst. Sci. 2008, 33, 27-35.
M. J. Raja, D. A. Xavier. Conditional Matching Preclusion Number for Butterfly Derived Networks. Inter. J. Pure Appl. Math. 2016, 7, 17-25.
J.-H. Park, Matching preclusion problem in restricted HL-graphs and recursive circulate g(2m, 4), Journal of KIISE 2008, 35, 60-65.
J.-H. Park, I. Ihm, Strong matching preclusion, Theor. Comput. Sci. 2011, 412, 6409-6419.
J.-H. Park, I. Ihm, Strong matching preclusion under the conditional fault model, Discrete Appl. Math 2013, 161, 1093-1105.
E. Cheng, J. Kelm, J. Renzi, Strong matching preclusion of (n, k)-star graphs, Theory. Comput. Sci. 2016, 615, 91--101.
E. Cheng, D. Lu, B. Xu, Strong matching preclusion of pancake graphs, J. Interconnection. Netw 2013, 14 (2), 1350007.
E. Cheng, S. Shah, V. Shah, D. E. Steffy, Strong matching preclusion for augmented cubes, Theor. Comput. Sci. 2013, 491, 71-77.
S. Wang, K. Feng, G. Zhang, Strong matching preclusion for k-ary n-cubes, Discrete Appl. Math 2013, 161, 3054-3062.
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.
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.
Y. Mao, Z. Wang, E. Cheng, C. Melekian, Strong matching preclusionnumber of graphs, Theor. Comput. Sci. 2018, 713, 11-20.
Z. Wang, Y. Mao, E. Cheng, J. Y. Zou, Matching preclusion number of graphs, Theor. Comput. Sci 2019, 759, 61-71.