Abstract
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\le \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 \le h\le g5^{\lfloor \frac{n}{2}\rfloor +r}\), where \(r=1, 2,\cdots , \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.
Similar content being viewed by others
Data availibility
Enquiries about data availability should be directed to the authors.
Notes
when \( s=0, ex_{m}(K_{5}^{n})=4a_{0}b_{0}5^{b_{0}}+2I_{a_{0}}5^{b_{0}}\)
References
Alsaleh O, Bella B, Hamdaoui B (2015) One-to-many node-disjoint paths routing in dense gaussian networks. Comput J 58(2):173–187
Fàbrega J, Fiol MA (1994) Extra connectivity of graphs with large girth. Discrete Math 127:163–170
Fàbrega J, Fiol MA (1996) On the extra connectivity of graphs. Discrete Math 155:49–57
Klešč M (1999) The crossing numbers of \(K_{5}\times P_{n}\). Tatra Mount Math Publ 18:63–68
Lai CN, Chen GH, Duh DR (2002) Constructing one-to-many disjoint paths in folded hypercubes. IEEE Trans Comput 51:33–45
Liang TT, Zhang MZ, Yang X (2022) Reliability analysis of the pentanary \(n\)-cube based on \(h\)-extra edge-connectivity with a concentration behavior. J Supercomput 78:15504–15531
Li XJ, Liu B, Ma MJ, Xu JM (2017) Many-to-many disjoint paths in hypercubes with faulty vertices. Discrete Appl Math 217:229–242
Li H, Yang WH (2013) Bounding the size of the subgraph induced by \(m\) vertices and extra edge-connectivity of hypercubes. Discrete Appl Math 161:2753–2757
Lü SX, Huang YQ (2008) On the crossing numbers of \(K_{5}\times S_{n}\). J Math Res Expos 28:445–459
Lü HZ, Wu TZ (2021) Unpaired many-to-many disjoint path cover of balanced hypercubes. Int J Found Comput Sci 32:943–956
Ma WH, Zhang MZ, Meng JX, Ma TL (2021) Exponential type of many-to-many edge disjoint paths on ternary \(n\)-cubes. J Parallel Distrib Comput 158:67–79
Ma Z, Cai J (2008) The crossing number of \(W_{5}\times S_{n}\). Acta Math Appl Sin-E 31:616–623
Menger K (1927) Zur allgemeinen Kurventheorie. Fund Math 10(1):96–115
Montejano LP, Sau I (2017) On the complexity of computing the \(k\)-restricted edge-connectivity of a graph. Theor Comput Sci 662:31–39
Niu RC, Xu M (2022) The unpaired many-to-many \(k\)-disjoint paths in bipartite hypercube-like networks. Theor Comput Sci 911:26–40
Sun YF, Wu CC, Zhang XY, Zhang Z (2020) Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs. J Comb Optim 44:1741–1752
Tian ZX, Zhang MZ, Feng X (2022) Reliability measure of the \(n\)-th cartesian product of complete graph \(K_{4}\) on \(h\)-extra edge-connectivity. Theor Comput Sci 922:46–60
Wei YL, Li RH, Yang WH (2021) The \(g\)-extra edge-connectivity of balanced hypercubes. J Interconnect Netw. https://doi.org/10.1142/S0219265921420081
Xu LQ, Zhou SM (2022) An \(O({\log }_2(N))\) algorithm for reliability assessment of augmented cubes based on \(h\)-extra edge-connectivity. J Supercomput 78:6739–6751
Yu ZC, Xu LQ, Yin SS, Guo LT (2022) Super vertex (edge)-connectivity of varietal hypercube. Symmetry. https://doi.org/10.3390/sym14020304
Zhang MZ, Ma WH, Ma TL (2021) Many-to-many disjoint paths in augmented cubes with exponential fault edges. IEEE Access 9:95382–95390
Zhang MZ, Meng JX, Yang WH, Tian YZ (2014) Reliability analysis of bijective connection networks in terms of the extra edge-connectivity. Inform Sci 279:374–382
Zhang MZ, Meng JX, Yang WH (2016) On the extra edge-connectivity of hypercubes. Appl Math J Chin Univ 31:198–204
Zhang MZ, Zhang LZ, Feng X, Lai HJ (2018) An \(O({\log }_2(N))\) algorithm for reliability evaluation of \(h\)-extra edge-connectivity of folded hypercubes. IEEE Trans Reliab 67:297–307
Zhang MZ, Zhang LZ, Feng X (2016) Reliability measures in relation to the \(h\)-extra edge-connectivity of folded hypercubes. Theor Comput Sci 615:71–77
Zhang MZ (2018) Edge isopermetric problem on graphs and the related applications. University of Xiamen, Xiamen, pp 68–77
Zhang QF, Xu LQ, Yang WH (2021) 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
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have not disclosed any competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work was supported by National Natural Science Foundation of China (No.12101528), Basic scientific research in universities of Xinjiang Uygur Autonomous Region (2024), Science and Technology Project of Xinjiang Uygur Autonomous Region (No. 2020D01C069), Doctoral Startup Foundation of Xinjiang University (No. 62031224736), Tianchi Ph.D Program (Grant No. tcbs201905) and Xinjiang Key Laboratory of Applied Mathematics, No.XJDX1401.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Liang, T., Zhang, M. & Liu, S. Concentration behavior: 50 percent of h-extra edge connectivity of pentanary n-cube with exponential faulty edges. J Comb Optim 47, 3 (2024). https://doi.org/10.1007/s10878-023-01098-3
Accepted:
Published:
DOI: https://doi.org/10.1007/s10878-023-01098-3