泡型图的强连通性
The Strong Connectivity of Bubble-Sort Graphs
DOI: 10.12677/AAM.2024.133107, PDF, 下载: 37  浏览: 68  国家自然科学基金支持
作者: 郭小丽, 王世英*：山西师范大学数学与计算机科学学院，山西 太原
关键词: 连通性；强连通性；强自然连通性；泡型图；Connectivity； Strong Connectivity； Strong Natural Connectivity； Bubble-Sort Graphs
摘要: 一个互联网络系统通常由一个简单无向连通图 G = (V (G), E(G)) 构成，其中 V (G) 和 E(G) 分别 表示互联网络中的处理器和处理器之间的通信链路。 在互联网络中，处理器或者通信链路出现故 章是不可避免的，而连通性和边连通性是评估互联网络容错性和可靠性的主要参数。 基于这种情 况，提出了互联网络的强连通性，强连通性允许处理器和通信链路同时发生故章。 在本文中，我 们研究了当 n ≥ 4 时，n-维泡型图 Bn 的强连通性和强自然连通性以及强自然边连通性等相关性 质。
Abstract: A network is usually modeled by a simple undirected graph G = (V (G), E(G)), where V (G) and E(G) represent processors and links between processors, respectively. In the interconnect network, the failure of processors or communication links is unavoidable. The connectivity and edge-connectivity of G are major parameters to evaluate the fault-tolerance and reliability of a network. Based on such circumstances, strong connectivity of the internet is proposed, it allows both processors and links to fail at the same time. In this paper, we study strong connectivity of Bn for n ≥ 4, including the strong natural connectivity and strong natural edge-connectivity of Bn and so on.
文章引用：郭小丽, 王世英. 泡型图的强连通性[J]. 应用数学进展, 2024, 13(3): 1156-1175. https://doi.org/10.12677/AAM.2024.133107

参考文献

[1] Araki, T. and Kikuchi, Y. (2007) Hamiltonian Laceability of Bubble-Sort Graphs with Edge Faults. Information Sciences, 177, 2679-2691.
https://doi.org/10.1016/j.ins.2007.01.017
[2] Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer, New York.
[3] Feng, Y., Hao, R. and Zhou, J. (2017) On Computing of a Conditional Edge Connectivity of Alternating Group Network. Linear and Multilinear Algebra, 65, 2494-2507.
https://doi.org/10.1080/03081087.2016.1277689
[4] Kikuchi, Y. and Araki, T. (2006) Edge-Bipancyclicity and Edge-Fault-Tolerant Bipancyclicity of Bubble-Sort Graphs. Information Processing Letters, 100, 52-59.
https://doi.org/10.1016/j.ipl.2006.05.012
[5] Shi, L. and Wu, P. (2017) Conditional Connectivity of Bubble Sort Graphs. Acta Mathematicae Applicatae Sinica, English Series, 33, 933-944.
https://doi.org/10.1007/s10255-017-0708-8
[6] Wang, S. and Yang, Y. (2012) Fault Tolerance in Bubble-Sort Graph Networks. Theoretical Computer Science, 421, 62-69.
https://doi.org/10.1016/j.tcs.2011.11.016
[7] Wang, M., Yang, W., Guo, Y. and Wang, S. (2016) Conditional Fault Tolerance in a Class of Cayley Graphs. International Journal of Computer Mathematics, 3, 67-82.
[8] Wang, Y. and Wang, S. (2021) Edge-Fault-Tolerant Strong Menger Edge Connectivity of Bubble-Sort Graphs. AIMS Mathematics, 6, 13210-13221.
https://doi.org/10.3934/math.2021763
[9] Zhou, S., Wang, J., Xu, X. and Xu, J. (2013) Conditional Fault Diagnosis of Bubble Sort Graphs under the PMC Model. Intelligence Computation and Evolutionary Computation. Advances in Intelligent Systems and Computing, 180, 53-59.
https://doi.org/10.1007/978-3-642-31656-2 8
[10] Gu, M., Hao, R., Tang, S. and Chang, J. (2020) Analysis on Component Connectivity of Bubble-Sort Star Graphs and Burnt Pancake Graphs. Discrete Applied Mathematics, 279, 80-91.
https://doi.org/10.1016/j.dam.2019.10.018
[11] Guo, J. and Lu, M. (2021) Edge-Fault-Tolerant Strong Menger Edge Connectivity of Bubble- Sort Star Graphs. Discrete Applied Mathematics, 297, 109-119.
https://doi.org/10.1016/j.dam.2021.03.006
[12] He, S., Hao, R. and Cheng, E. (2018) Strongly Menger-Edge-Connectedness and Strongly Menger-Vertex-Connectedness of Regular Networks. Theoretical Computer Science, 731, 50- 67.
https://doi.org/10.1016/j.tcs.2018.04.001
[13] Li, X., Liu, M., Yan, Z. and Xu, J. (2019) On Conditional Fault Tolerance of Hierarchical Cubic Networks. Theoretical Computer Science, 761, 1-6.
https://doi.org/10.1016/j.tcs.2018.07.021
[14] Wang, S. and Wang, M. (2019) The Strong Connectivity of Bubble-Sort Star Graphs. The Computer Journal, 62, 1-15.
[15] Wang, S., Wang, Z. and Wang, M. (2017) The 2-Good-Neighbor Connectivity and 2-Good- Neighbor Diagnosability of Bubble-Sort Star Graph Networks. Discrete Applied Mathematics, 217, 691-706.
https://doi.org/10.1016/j.dam.2016.09.047
[16] Wang, S., Wang, Z. and Wang, M. (2016) The 2-Extra Connectivity and 2-Extra Diagnosability of Bubble-Sort Star Graph Networks. The Computer Journal, 59, 1839-1856.
https://doi.org/10.1093/comjnl/bxw037
[17] Akers, S.B. and Krishnamurthy, B. (1989) A Group Theoretic Model for Symmetric Intercon- nection Networks. IEEE Transaction on Computers, 38, 555-566.
https://doi.org/10.1109/12.21148
[18] 徐敏, 经拎. Bubble-Sort网络的连通度和超连通度[J]. 应用数学学报, 2012(5): 789-794.

为你推荐