Edge-fault-tolerant strong Menger edge connectivity of bubble-sort graphs

Yanling Wang; Shiying Wang; Yanling Wang; Shiying Wang

doi:10.3934/math.2021763

AIMS Mathematics

2021, Volume 6, Issue 12: 13210-13221. doi: 10.3934/math.2021763

Previous Article Next Article

Research article

Edge-fault-tolerant strong Menger edge connectivity of bubble-sort graphs

Yanling Wang ^,,
Shiying Wang

College of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan 453007, PR China

Received: 04 August 2021 Accepted: 09 September 2021 Published: 15 September 2021
MSC : 05C40, 68M15

This paper studies the edge-fault-tolerant strong Menger edge connectivity of $ n $-dimensional bubble-sort graph $ B_{n} $. We give the values of faulty edges that $ B_{n} $ can tolerant when $ B_{n} $ is strongly Menger edge connected under two conditions. When there are $ (n-3) $ faulty edges removed from $ B_{n} $, the $ B_{n} $ network is still working and it is strongly Menger edge connected. When the condition of any vertex in $ B_{n} $ has at least two neighbors is imposed, the number of faulty edges that can removed from $ B_{n} $ is $ (2n-6) $ when $ B_{n} $ is also strongly Menger edge connected. And two special cases are used to illustrate the correctness of the conclusions. The conclusions can help improve the reliability of the interconnection networks.
- edge-disjoint paths,
- fault-tolerant,
- strong Menger edge connectivity,
- bubble-sort graph
Citation: Yanling Wang, Shiying Wang. Edge-fault-tolerant strong Menger edge connectivity of bubble-sort graphs[J]. AIMS Mathematics, 2021, 6(12): 13210-13221. doi: 10.3934/math.2021763

Related Papers:

Abstract

This paper studies the edge-fault-tolerant strong Menger edge connectivity of $ n $-dimensional bubble-sort graph $ B_{n} $. We give the values of faulty edges that $ B_{n} $ can tolerant when $ B_{n} $ is strongly Menger edge connected under two conditions. When there are $ (n-3) $ faulty edges removed from $ B_{n} $, the $ B_{n} $ network is still working and it is strongly Menger edge connected. When the condition of any vertex in $ B_{n} $ has at least two neighbors is imposed, the number of faulty edges that can removed from $ B_{n} $ is $ (2n-6) $ when $ B_{n} $ is also strongly Menger edge connected. And two special cases are used to illustrate the correctness of the conclusions. The conclusions can help improve the reliability of the interconnection networks.

References

[1]	Z. Wang, Y. Zou, Y. Liu, Z. Meng, Distributed control algorithm for leader-follower formation tracking of multiple quadrotors: theory and experiment, IEEE-ASME T. Mech., 26 (2020), 1095–1105.
[2]	Y. Zou, L. Wang, Z. Meng, Distributed localization and circumnavigation algorithms for a multiagent system with persistent and intermittent bearing measurements, IEEE Trans. Contr. Syst. T., 29 (2021), 2092–2101. doi: 10.1109/TCST.2020.3032395
[3]	B. N. Alhasnawi, B. H. Jasim, B. E. Sedhom, Distributed secondary consensus fault tolerant control method for voltage and frequency restoration and power sharing control in multi-agent microgrid, Int. J. Elec. Power, 133 (2021), 107251. doi: 10.1016/j.ijepes.2021.107251
[4]	Y. Wang, S. Wang, The 3-good-neighbor connectivity of modified bubble-sort graphs, Math. Probl. Eng., 2020 (2020), 7845987.
[5]	B. N. Alhasnawi, B. H. Jasim, P. Siano, J. M. Guerrero, A novel real-time electricity scheduling for home energy management system using the internet of energy, Energies, 14 (2021), 1–29.
[6]	B. N. Alhasnawi, B. H. Jasim, SCADA controlled smart home using Raspberry Pi3, 2018 International Conference on Advance of Sustainable Engineering and its Application (ICASEA). IEEE, 2018.
[7]	B. N. Alhasnawi, B. H. Jasim, M. D. Esteban, A new robust energy management and control strategy for a hybrid microgrid system based on green energy, Sustainability, 12 (2020), 1–28.
[8]	B. N. Alhasnawi, B. H. Jasim, B. A. Issa, Internet of things (IoT) for smart precision agriculture, IJEEE, 16 (2020), 28–38.
[9]	B. N. Alhasnawi, B. H. Jasim, B. E. Sedhom, E. Hossain, J. M. Guerrero, A new decentralized control strategy of microgrids in the internet of energy paradigm, Energies, 14 (2021), 1–34.
[10]	E. Oh, J. Chen, On strong Menger-connectivity of star graphs, Discret. Appl. Math., 129 (2003), 499–511. doi: 10.1016/S0166-218X(02)00600-5
[11]	E. Oh, J. Chen, Strong fault tolerance: Parallel routing in star networks with faults, J. Interconnect. Netw., 4 (2003), 113–126. doi: 10.1142/S0219265903000763
[12]	Y. Qiao, W. Yang, Edge disjoint paths in hypercubes and folded hypercubes with conditonal faults, Appl. Math. Comput., 294 (2017), 96–101.
[13]	S. Li, J. Tu, C. Yu, The generalized 3-connectivity of star graphs and bubble-sort graphs, Appl. Math. Comput., 271 (2016), 41–46.
[14]	W. Yang, H. Li, J. Meng, Conditional connectivity of Cayley graphs generated by transposition trees, Inform. Process. Lett., 110 (2010), 1027–1030. doi: 10.1016/j.ipl.2010.09.001
[15]	L. M. Shih, C. F. Chiang, L. H. Hsu, J. J. M. Tan, Strong Menger connectivity with conditional faults on the class of hypercube-like networks, Inform. Process. Lett., 106 (2008), 64–69. doi: 10.1016/j.ipl.2007.10.009
[16]	K. Menger, Zur allgemeinen kurventheorie, Fund. Math., 10 (1927), 96–115. doi: 10.4064/fm-10-1-96-115
[17]	P. Li, M. Xu. Fault-tolerant strong Menger (edge) connectivity and 3-extra edge-connectivity of balanced hypercubes, Theoret. Comput. Sci., 707 (2018), 56–68. doi: 10.1016/j.tcs.2017.10.017
[18]	Y. C. Chen, M. H. Chen, J. J. M. Tan, Maximally local connectivity and connected components of augmented cubes, Inform. Sci., 273 (2014), 387–392. doi: 10.1016/j.ins.2014.03.022
[19]	H. Cai, H. Liu, M. Lu, Fault-tolerant maximal local-connectivity on bubble-sort star graphs, Discret. Appl. Math., 181 (2015), 33–40. doi: 10.1016/j.dam.2014.10.006
[20]	W. Yang, S. Zhao, S. Zhang, Strong Menger connectivity with conditional faults of folded hypercubes, Inform. Process. Lett., 125 (2017), 30–34. doi: 10.1016/j.ipl.2017.05.001
[21]	P. Li, M. Xu, Edge-fault-tolerant strong Menger edge connectivity on the class of hypercube-like networks, Discret. Appl. Math., 259 (2019), 145–152. doi: 10.1016/j.dam.2018.12.024
[22]	J. Guo, M. Li, Edge-fault-tolerant strong Menger edge connectivity of bubble-sort star graphs, Discret. Appl. Math., 297 (2021), 109–119. doi: 10.1016/j.dam.2021.03.006
[23]	S. B. Akers, B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38 (1989), 555–566. doi: 10.1109/12.21148
[24]	H. Shi, P. Niu, J. Lu, One conjecture of bubble-sort graphs, Inform. Process. Lett., 111 (2011), 926–929. doi: 10.1016/j.ipl.2011.06.005
[25]	E. Cheng, L. Lipták, Linearly many faults in Cayley graphs generated by transposition trees, Inform. Sci., 177 (2007), 4877–4882. doi: 10.1016/j.ins.2007.05.034
[26]	E. Cheng, L. Lipták, N. Shawash, Orienting Cayley graphs generated by transposition trees, Comput. Math. Appl., 55 (2008), 2662–2672. doi: 10.1016/j.camwa.2007.10.016
[27]	M. Xu, The connectivity and super connectivity of bubble-sort graph, Acta Math. Appl. Sin., 35 (2012), 789–794.

Reader Comments

Your name:*

Email:*
© 2021 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)