Matching preclusion and conditional matching preclusion for hierarchical cubic networks

Jinyu Zou; Haizhen Ren; Jinyu Zou; Haizhen Ren

doi:10.3934/math.2022729

AIMS Mathematics

2022, Volume 7, Issue 7: 13225-13236. doi: 10.3934/math.2022729

Previous Article Next Article

Research article

Matching preclusion and conditional matching preclusion for hierarchical cubic networks

Jinyu Zou ¹,
Haizhen Ren ^{2,3,4
,
,}

1.
Department of Basic Course, Qinghai University, Xining, Qinghai 810016, China
2.
School of Mathematics and Statistics, Qinghai Normal University, Xining, Qinghai 810008, China
3.
The State Key Laboratory of Tibetan Information Processing and Application, Xining, China
4.
Academy of Plateau, Science and Sustainability, Xining, China

Received: 23 January 2022 Revised: 12 April 2022 Accepted: 21 April 2022 Published: 11 May 2022
MSC : 05C05, 05C12, 05C76

Matching preclusion originates from the measurement of interconnection network robustness in the event of edge failure. Conditional matching preclusion belongs to generalized matching preclusion. We obtain the matching preclusion number and conditional matching preclusion number for hierarchical cubic network($ HCN_n $). Additionally, all the optimal (conditional) matching preclusion sets of $ HCN_n $ are characterized, which generalize some related results of Birgham et al. and Cheng et al.
- matching,
- matching preclusion,
- conditional matching preclusion,
- hierarchical cubic network $ HCN_n $
Citation: Jinyu Zou, Haizhen Ren. Matching preclusion and conditional matching preclusion for hierarchical cubic networks[J]. AIMS Mathematics, 2022, 7(7): 13225-13236. doi: 10.3934/math.2022729

Related Papers:

Abstract

Matching preclusion originates from the measurement of interconnection network robustness in the event of edge failure. Conditional matching preclusion belongs to generalized matching preclusion. We obtain the matching preclusion number and conditional matching preclusion number for hierarchical cubic network($ HCN_n $). Additionally, all the optimal (conditional) matching preclusion sets of $ HCN_n $ are characterized, which generalize some related results of Birgham et al. and Cheng et al.

References

[1]	R. C. Birgham, F. Harry, E. C. Biolin, J. Yellen, Perfect matching preclusion, Congr. Numer., 174 (2005), 185–192.
[2]	E. Cheng, L. Lipták, Matching preclusion for some interconnection networks, Networks, 50 (2007), 173–180. http://dx.doi.org/10.1002/net.20187 doi: 10.1002/net.20187
[3]	E. Cheng, L. Lensik. M. Lipman, L. Lipták, Matching preclusion for alternating group graphs and their generalizations, Int. J. Found. Comp. Sci., 19 (2008), 1413–1437. http://dx.doi.org/10.1142/S0129054108006364 doi: 10.1142/S0129054108006364
[4]	E. Cheng, L. Lensik. M. Lipman, L. Lipták, Conditional matching preclusion sets, Inf. Sci., 179 (2009), 1092–1101. http://dx.doi.org/10.1016/j.ins.2008.10.029 doi: 10.1016/j.ins.2008.10.029
[5]	E. Cheng, R. Jia, D. Lu, Matching preclusion and conditional matching preclusion for augmented cubes, J. of Interconnection Networks, 11 (2010), 35–60. http://dx.doi.org/10.1142/S0219265910002726 doi: 10.1142/S0219265910002726
[6]	W. Chang, E. Cheng, Strong matching preclusion of 2-matching composition networks, Congr. Numer., 224 (2015), 91–104.
[7]	H. Lü, X. Li, H. Zhang, NP-completeness of anti-Kekule and matching preclusion problem, J. Amer. Math. Soc., 2017 (2017), arXiv: 1706.09321. http://dx.doi.org/10.48550/arXiv.1706.09321
[8]	R. Lin, H. Zhang, W. Zhao, Matching preclusion for direct product of regular graphs, Discrete Appl. Math., 277 (2020), 221–230. http://dx.doi.org/10.1016/j.dam.2019.08.016 doi: 10.1016/j.dam.2019.08.016
[9]	R. Lin, Conditional matching preclusion for regular bipartite graphs and their Cartesian product, Discrete Appl. Math., 299 (2021), 17–25. http://dx.doi.org/10.1016/j.dam.2021.04.011 doi: 10.1016/j.dam.2021.04.011
[10]	H. Lv, X. Li, H. Zhang, Matching preclusion for balanced hypercubes, Theor. Comput. Sci., 465 (2012), 10–20. http://dx.doi.org/10.1016/j.tcs.2012.09.020 doi: 10.1016/j.tcs.2012.09.020
[11]	E. Cheng, M. Lipman, L. Lipták, D. Sherman, Conditional matching preclusion for the arrangement graphs, Theor. Comput. Sci., 412 (2011), 6279–6289. http://dx.doi.org/10.1016/j.tcs.2011.07.007 doi: 10.1016/j.tcs.2011.07.007
[12]	S. Wang, R. Wang, S. Lin, J. Li, Matching preclusion for $k$-ary $n$-cubes, Discrete Appl. Math., 158 (2010), 174–182. http://dx.doi.org/10.1016/j.topol.2011.01.008 doi: 10.1016/j.topol.2011.01.008
[13]	Y. Mao, E. Cheng, A concise survey of matching preclusion in interconnection networks, J. Interconnect. Networks, 19 (2019), 1940006. http://dx.doi.org/10.1142/S0219265919400061 doi: 10.1142/S0219265919400061
[14]	K. Ghose, K. R. Desai, Hierarchical cubic network, IEEE Trans. Parallel Distrib Syst., 6 (1995), 427–435. http://dx.doi.org/10.1109/71.372797 doi: 10.1109/71.372797
[15]	S. Zhou, S. Song, X. Yang, L. Chen, On the conditional fault tolerance and diagnosability of hierarchical cubic networks, Theor. Comput. Sci., 609 (2016), 421–433. http://dx.doi.org/10.1016/j.tcs.2015.10.030 doi: 10.1016/j.tcs.2015.10.030

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)