|
|
星图的R1-限制性点割
|
Abstract:
互联网络的拓扑结构可以用图论模型来描述，因此图论在研究网络问题时扮演着重要角色。连通度是衡量一个网络容错性和可靠性的重要指标。然而，在实际情况中，网络中一个点的所有邻点同时发生故障的概率较小，因此经典连通度在一定程度上低估了互联网络的容错性。为了更准确地评估网络的连通性，引入了条件连通度的概念，并进一步提出了Rk-连通度的概念，使得连通度问题更具有现实意义。本文主要研究并刻画了星图的全部基数最小的R1-限制性点割。
The topology of the Internet can be described using graph theory models, thus graph theory plays an important role in studying network issues. Connectivity is a crucial metric for assessing the fault tolerance and reliability of a network. However, in practical scenarios, the probability of all neighbors of a node in the network failing simultaneously is very small. Therefore, classic connectivity to some extent underestimates the fault tolerance of the Internet. To more accurately evaluate network connectivity, the concept of conditional connectivity has been introduced, and further, the concept of Rk-connectivity has been proposed, making the connectivity problem more practically significant. This paper primarily studies and characterizes the minimum cardinality R1-restricted cut of star graphs.
| [1] | Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer, New York. https://doi.org/10.1007/978-1-84628-970-5 |
| [2] | Harary, F. (1983) Conditional Connectivity. Networks, 13, 347-357. https://doi.org/10.1002/net.3230130303 |
| [3] | Esfahanian, A.H. (1989) Generalized Measures of Fault Tolerance with Application to N-Cube Networks. IEEE Transactions on Computers, 38, 1586-1591. https://doi.org/10.1109/12.42131 |
| [4] | Hu, X.M., Tian, Y.Z. and Meng, J.X. ((2018)) Super Rk-Vertex-Connectedness. Applied Mathematics and Computation, 339, 812-819. https://doi.org/10.1016/j.amc.2018.07.012 |
| [5] | Wang, G.L., Shi, H.Z., Hou, F.F. and Bai, Y.L. (2015) Some Conditional Vertex Connectivities of Complete-Trasposition Graphs. Information Sciences, 295, 536-543. https://doi.org/10.1016/j.ins.2014.10.032 |
| [6] | Yang, W.H., Li, H.Z. and Meng, J.X. (2010) Conditional Connectivity of Cayley Graphs Generated by Transposition Trees. Information Processing Letters, 110, 1027-1030. https://doi.org/10.1016/j.ipl.2010.09.001 |
| [7] | Yang, W.H. (2018) A King of Conditional Connectivity of Cayley Graphs Generated by K-Trees. Discrete Applied Mathematics, 237, 132-138. https://doi.org/10.1016/j.dam.2017.11.025 |
| [8] | Yu, X.M. and Huang, X.H. (2013) A King of Conditional Connectivity of Cayley Graphs Generated by Unicyclic Graphs. Information Sciences, 243, 86-94. https://doi.org/10.1016/j.ins.2013.04.011 |
| [9] | Tu, J.H., Zhou, Y.K. and Su, G.F. (2017) A Kind of Conditional Connectivity of Cayley Graphs Generated by Wheel Graphs. Applied Mathematics and Computation, 301, 177-186. https://doi.org/10.1016/j.amc.2016.12.015 |
| [10] | Cheng, E. and Lipták, L. (2007) Fault Resiliency of Cayley Graphs Generated by Transpositions. International Journal of Foundations of Computer Science, 5, 1005-1022. https://doi.org/10.1142/S0129054107005108 |
| [11] | Wan, M. and Zhang, Z. (2009) A Kind of Conditional Vertex Connectivity of Star Graphs. Applied Mathematics Letters, 22, 264-267. https://doi.org/10.1016/j.aml.2008.03.021 |
| [12] | Cheng, E., Lipman, M.J. and Park, H. (2001) Super Connectivity of Star Graphs, Alternating Group Graphs and Split-Stars. ARS Combinatoria, 59, 107-116. |
| [13] | Hu, S.C. and Yang, C.B. (1997) Fault Tolerance on Star Graphs. International Journal of Foundations of Computer Science, 8, 127-142. https://doi.org/10.1142/S0129054197000112 |
