×

Concentration behavior: 50 percent of \(h\)-extra edge connectivity of pentanary \(n\)-cube with exponential faulty edges. (English) Zbl 1541.90304

Summary: Edge disjoint paths have a closed relationship with edge connectivity and are anticipated to garner increased attention in the study of the reliability and edge fault tolerance of a readily scalable interconnection network. Note that this interconnection network is always modeled as a connected graph \(G\). The minimum of some of modified edge-cuts of a connected graph \(G\), also known as the \(h\)-extra edge-connectivity of a graph \(G (\lambda_h (G))\), is defined as the maximum number of the edge disjoint paths connecting any two disjoint connected subgraphs with \(h\) vertices in the graph \(G\). From the perspective of edge-cut, the smallest cardinality of a collection of edges, whose removal divides the whole network into several connected subnetworks having at least \(h\) vertices, is the \(h\)-extra edge-connectivity of the underlying topological architecture of an interconnection network \(G\). This paper demonstrates that the \(h\)-extra edge-connectivity of the pentanary \(n\)-cube \((\lambda_h (K_5^n))\) appears a concentration behavior for around 50 percent of \(h\leq \lfloor 5^n /2\rfloor\) as \(n\) approaches infinity. Let \(e=1\) for \(n\) is even and \(e=0\) for \(n\) is odd. It mainly concentrates on the value \([4g(\lceil \frac{n}{2}\rceil -r)-g(g-1)]5^{\lfloor \frac{n}{2}\rfloor +r}\) for \(g5^{\lfloor \frac{n}{2}\rfloor +r}-\lfloor \frac{[(g-1)^2 +1]5^{2r+e}}{3}\rfloor \leq h\leq g5^{\lfloor \frac{n}{2}\rfloor +r}\), where \(r=1, 2,\dots, \lceil \frac{n}{2}\rceil -2\), \(g\in \{1,2,3,4\}\); \(r=\lceil \frac{n}{2}\rceil -1\), \(g\in \{1,2\}\). Furthermore, it is shown that the above upper bound and lower bound of \(h\) are sharp.

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
Full Text: DOI

References:

[1] Alsaleh, O.; Bella, B.; Hamdaoui, B., One-to-many node-disjoint paths routing in dense gaussian networks, Comput J, 58, 2, 173-187 (2015) · doi:10.1093/comjnl/bxt142
[2] Fàbrega, J.; Fiol, MA, Extra connectivity of graphs with large girth, Discrete Math, 127, 163-170 (1994) · Zbl 0797.05058 · doi:10.1016/0012-365X(92)00475-7
[3] Fàbrega, J.; Fiol, MA, On the extra connectivity of graphs, Discrete Math, 155, 49-57 (1996) · Zbl 0857.05064 · doi:10.1016/0012-365X(94)00369-T
[4] Klešč, M., The crossing numbers of \(K_5\times P_n\), Tatra Mount Math Publ, 18, 63-68 (1999) · Zbl 0951.05030
[5] Lai, CN; Chen, GH; Duh, DR, Constructing one-to-many disjoint paths in folded hypercubes, IEEE Trans Comput, 51, 33-45 (2002) · Zbl 1392.68328 · doi:10.1109/12.980015
[6] Liang, TT; Zhang, MZ; Yang, X., Reliability analysis of the pentanary \(n\)-cube based on \(h\)-extra edge-connectivity with a concentration behavior, J Supercomput, 78, 15504-15531 (2022) · doi:10.1007/s11227-022-04489-1
[7] Li, XJ; Liu, B.; Ma, MJ; Xu, JM, Many-to-many disjoint paths in hypercubes with faulty vertices, Discrete Appl Math, 217, 229-242 (2017) · Zbl 1358.05150 · doi:10.1016/j.dam.2016.09.013
[8] Li, H.; Yang, WH, Bounding the size of the subgraph induced by \(m\) vertices and extra edge-connectivity of hypercubes, Discrete Appl Math, 161, 2753-2757 (2013) · Zbl 1285.05129 · doi:10.1016/j.dam.2013.04.009
[9] Lü, SX; Huang, YQ, On the crossing numbers of \(K_5\times S_n\), J Math Res Expos, 28, 445-459 (2008) · Zbl 1199.05071
[10] Lü, HZ; Wu, TZ, Unpaired many-to-many disjoint path cover of balanced hypercubes, Int J Found Comput Sci, 32, 943-956 (2021) · Zbl 1520.68124 · doi:10.1142/S0129054121500301
[11] Ma, WH; Zhang, MZ; Meng, JX; Ma, TL, Exponential type of many-to-many edge disjoint paths on ternary \(n\)-cubes, J Parallel Distrib Comput, 158, 67-79 (2021) · doi:10.1016/j.jpdc.2021.07.020
[12] Ma, Z.; Cai, J., The crossing number of \(W_5\times S_n\), Acta Math Appl Sin-E, 31, 616-623 (2008) · Zbl 1174.05006
[13] Menger, K., Zur allgemeinen Kurventheorie. Fund Math, 10, 1, 96-115 (1927) · JFM 53.0561.01 · doi:10.4064/fm-10-1-96-115
[14] Montejano, LP; Sau, I., On the complexity of computing the \(k\)-restricted edge-connectivity of a graph, Theor Comput Sci, 662, 31-39 (2017) · Zbl 1356.68107 · doi:10.1016/j.tcs.2016.12.006
[15] Niu, RC; Xu, M., The unpaired many-to-many \(k\)-disjoint paths in bipartite hypercube-like networks, Theor Comput Sci, 911, 26-40 (2022) · Zbl 1535.68223 · doi:10.1016/j.tcs.2022.02.003
[16] Sun, YF; Wu, CC; Zhang, XY; Zhang, Z., Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs, J Comb Optim, 44, 1741-1752 (2020) · Zbl 1502.90155 · doi:10.1007/s10878-020-00541-z
[17] Tian, ZX; Zhang, MZ; Feng, X., Reliability measure of the \(n\)-th cartesian product of complete graph \(K_4\) on \(h\)-extra edge-connectivity, Theor Comput Sci, 922, 46-60 (2022) · Zbl 1535.68232 · doi:10.1016/j.tcs.2022.04.010
[18] Wei, YL; Li, RH; Yang, WH, The \(g\)-extra edge-connectivity of balanced hypercubes, J Interconnect Netw (2021) · doi:10.1142/S0219265921420081
[19] Xu, LQ; Zhou, SM, An \(O({\log }_2(N))\) algorithm for reliability assessment of augmented cubes based on \(h\)-extra edge-connectivity, J Supercomput, 78, 6739-6751 (2022) · doi:10.1007/s11227-021-04129-0
[20] Yu, ZC; Xu, LQ; Yin, SS; Guo, LT, Super vertex (edge)-connectivity of varietal hypercube, Symmetry (2022) · doi:10.3390/sym14020304
[21] Zhang, MZ; Ma, WH; Ma, TL, Many-to-many disjoint paths in augmented cubes with exponential fault edges, IEEE Access, 9, 95382-95390 (2021) · doi:10.1109/ACCESS.2021.3095370
[22] Zhang, MZ; Meng, JX; Yang, WH; Tian, YZ, Reliability analysis of bijective connection networks in terms of the extra edge-connectivity, Inform Sci, 279, 374-382 (2014) · Zbl 1354.68027 · doi:10.1016/j.ins.2014.03.125
[23] Zhang, MZ; Meng, JX; Yang, WH, On the extra edge-connectivity of hypercubes, Appl Math J Chin Univ, 31, 198-204 (2016) · Zbl 1363.05147 · doi:10.1007/s11766-016-3247-9
[24] Zhang, MZ; Zhang, LZ; Feng, X.; Lai, HJ, An \(O({\log }_2(N))\) algorithm for reliability evaluation of \(h\)-extra edge-connectivity of folded hypercubes, IEEE Trans Reliab, 67, 297-307 (2018) · doi:10.1109/TR.2017.2779130
[25] Zhang, MZ; Zhang, LZ; Feng, X., Reliability measures in relation to the \(h\)-extra edge-connectivity of folded hypercubes, Theor Comput Sci, 615, 71-77 (2016) · Zbl 1334.68032 · doi:10.1016/j.tcs.2015.11.049
[26] Zhang, MZ, Edge isopermetric problem on graphs and the related applications, 68-77 (2018), Xiamen: University of Xiamen, Xiamen
[27] Zhang, QF; Xu, LQ; Yang, WH, Reliability analysis of the augmented cubes in terms of the extra edge-connectivity and the component edge-connectivity, J Parallel Distrib Comput, 147, 124-131 (2021) · doi:10.1016/j.jpdc.2020.08.009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.