极大3限制边连通图的充分条件
Sufficient Conditions for Graphs to Be Maximally 3-Restricted Edge-Connected
摘要: k限 制 边 连 通 度 是 度 量 网 络 可 靠 性 的 重 要 参 数。 设G = (V, E)是 一 个 连 通 网 络。 称 一 个 边 集 合S ⊆ E 是一个k限制边割，如果G − S的每个连通分支至少有k个顶点。 称G的所有k限制边 割中所含边数最少的边割的基数为G的k限制边连通度，记为λk (G)。 定义ξk (G)  =  min{[X, Y ]:|X| = k，G[X]连通，Y = V (G)\X}。 称网络G是极大k限制边连通的，如果λk (G) = ξk (G)。 给出了网络是极大3限制边连通的一些充分条件。
Abstract: The k-restricted edge connectivity is an important index to measure the reliability of networks. For a connected network G = (V, E), an edge set S ⊆ E is a k-restricted edge cut if G − S is disconnected and every component of G − S has at least k vertices. The k-restricted edge connectivity of G, denoted by λk (G), is defined as the cardinality of a minimum k-restricted edge cut. Let ξk (G) = min{|[X, Y ]| : |X| = k, G[X] is connected}, where Y = V \X. A connected network G is maximally k-restricted edge connected if λk (G) = ξk (G). In this paper, some sufficient conditions are presented for networks to be maximally 3-restricted edge connected.
文章引用：张磊. 极大3限制边连通图的充分条件[J]. 应用数学进展, 2019, 8(3): 381-388. https://doi.org/10.12677/AAM.2019.83043

参考文献

[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] F`abrega, J. and Foil, M.A. (1996) On the Extraconnectivity of Graphs. Discrete Mathematics, 155, 49-57.
[3] Wang, S.Y., Zhang, L. and Lin, S.W. (2012) A Neighborhood Condition for Graphs to Be Maximally k-Restricted Edge Connected. Information Processing Letters, 112, 95-97.
https://doi.org/10.1016/j.ipl.2011.10.012
[4] Guo, L.T., Yang, W.H. and Guo, X.F. (2011) On a Kind of Reliability Analysis of Networks. Applied Mathematics and Computation, 218, 2711-2715.
https://doi.org/10.1016/j.amc.2011.08.010
[5] Yuan, J. and Liu, A.X. (2016) Sufficient Conditions for Triangle-Free Graphs to Be Super k-Restricted Edge-Connected. Information Processing Letters, 116, 163-167.
https://doi.org/10.1016/j.ipl.2015.09.005
[6] Hong, W.-S. and Hsieh, S.-Y. (2013) Extra Edge Connectivity of Hypercube-Like Networks. International Journal of Parallel, Emergent and Distributed Systems, 28, 123-133.
https://doi.org/10.1080/17445760.2011.650696
[7] Chang, N.-W., Tsai, C.-Y. and Hsieh, S.-Y. (2014) On 3-Extra Connectivity and 3-Extra Edge Connectivity of Folded Hypercubes. IEEE Transactions on Computers, 63, 1594-1600.
https://doi.org/10.1109/TC.2013.10
[8] Wang, S.Y. and Zhang, L. (2014) Sufficient Conditions for k-Restricted Edge Connected Graph-s. Theoretical Computer Science, 577, 66-75.
https://doi.org/10.1016/j.tcs.2014.08.018
[9] Abdol-Hossein, E. and Louis, H.S. (1988) On Computing a Conditional Edge-Connectivity of a Graph. Information Processing Letters, 27, 195-199.
https://doi.org/10.1016/0020-0190(88)90025-7
[10] Boesch, F.T. (1986) On Unreliability Polynomials and Graph Connectivity in Reliable Network Synthesis. Journal of Graph Theory, 10, 339-352.
https://doi.org/10.1002/jgt.3190100311
[11] Deng, H.Y., Chen, J., Li, Q.L., Li, R.H. and Gao, Q.J. (2004) On the Construction of Most Reliable Networks. Discrete Applied Mathematics, 140, 19-33.
https://doi.org/10.1016/j.dam.2003.06.003
[12] Balbuena, C., Marcote, X. and Garc´ıa-V´azquez, P. (2005) On Restricted Connectivities of Permutation Graphs. Networks, 45, 113-118.
https://doi.org/10.1002/net.20056
[13] Meng, J.X. (2003) Optimally Super-Edge-Connected Transitive Graphs. Discrete Mathematics, 260, 239-248.
https://doi.org/10.1016/S0012-365X(02)00675-1
[14] F`abrega, J. and Foil, M.A. (1994) Extraconnectivity of Graphs with Large Girth. Discrete Mathematics, 127, 163-170.
https://doi.org/10.1016/0012-365X(92)00475-7
[15] Zhang, Z. and Yuan, J.J. (2007) Degree Conditions for Restricted-Edge-Connectivity and Isoperimetric-Edge-Connectivity to Be Optimal. Discrete Mathematics, 307, 293-298.
https://doi.org/10.1016/j.disc.2006.06.028
[16] 张国珍. 极大限制边连通网络的充分条件[J]. 计算机工程与应用, 2017, 53(8): 19-22.
[17] Li, Q.L. and Li, Q. (1998) Reliability Analysis of Circulant Graphs. Networks, 31, 61-65.
https://doi.org/10.1002/(SICI)1097-0037(199803)31:2(61::AID-NET1)3.0.CO;2-H
[18] Wang, S.Y., Lin, S.W. and Li, C.F. (2009) Sufficient Conditions for Super k-Restricted Edge Connectivity in Graphs of Diameter 2. Discrete Mathematics, 309, 908-919.
https://doi.org/10.1016/j.disc.2008.01.037

为你推荐