[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Concentration behavior: 50 percent of h-extra edge connectivity of pentanary n-cube with exponential faulty edges

Published: 24 January 2024 Publication History

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 (λ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 (λh(K5n)) appears a concentration behavior for around 50 percent of h5n/2 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(n2-r)-g(g-1)]5n2+r for g5n2+r-[(g-1)2+1]52r+e3hg5n2+r, where r=1,2,,n2-2, g{1,2,3,4}; r=n2-1, g{1,2}. Furthermore, it is shown that the above upper bound and lower bound of h are sharp.

References

[1]
Alsaleh O, Bella B, and Hamdaoui B One-to-many node-disjoint paths routing in dense gaussian networks Comput J 2015 58 2 173-187
[2]
Fàbrega J and Fiol MA Extra connectivity of graphs with large girth Discrete Math 1994 127 163-170
[3]
Fàbrega J and Fiol MA On the extra connectivity of graphs Discrete Math 1996 155 49-57
[4]
Klešč M The crossing numbers of K5×Pn Tatra Mount Math Publ 1999 18 63-68
[5]
Lai CN, Chen GH, and Duh DR Constructing one-to-many disjoint paths in folded hypercubes IEEE Trans Comput 2002 51 33-45
[6]
Liang TT, Zhang MZ, and Yang X Reliability analysis of the pentanary n-cube based on h-extra edge-connectivity with a concentration behavior J Supercomput 2022 78 15504-15531
[7]
Li XJ, Liu B, Ma MJ, and Xu JM Many-to-many disjoint paths in hypercubes with faulty vertices Discrete Appl Math 2017 217 229-242
[8]
Li H and Yang WH Bounding the size of the subgraph induced by m vertices and extra edge-connectivity of hypercubes Discrete Appl Math 2013 161 2753-2757
[9]
Lü SX and Huang YQ On the crossing numbers of K5×Sn J Math Res Expos 2008 28 445-459
[10]
Lü HZ and Wu TZ Unpaired many-to-many disjoint path cover of balanced hypercubes Int J Found Comput Sci 2021 32 943-956
[11]
Ma WH, Zhang MZ, Meng JX, and Ma TL Exponential type of many-to-many edge disjoint paths on ternary n-cubes J Parallel Distrib Comput 2021 158 67-79
[12]
Ma Z and Cai J The crossing number of W5×Sn Acta Math Appl Sin-E 2008 31 616-623
[13]
Menger K Zur allgemeinen Kurventheorie. Fund Math 1927 10 1 96-115
[14]
Montejano LP and Sau I On the complexity of computing the k-restricted edge-connectivity of a graph Theor Comput Sci 2017 662 31-39
[15]
Niu RC and Xu M The unpaired many-to-many k-disjoint paths in bipartite hypercube-like networks Theor Comput Sci 2022 911 26-40
[16]
Sun YF, Wu CC, Zhang XY, and Zhang Z Computation and algorithm for the minimum k-edge-connectivity of graphs J Comb Optim 2020 44 1741-1752
[17]
Tian ZX, Zhang MZ, and Feng X Reliability measure of the n-th cartesian product of complete graph K4 on h-extra edge-connectivity Theor Comput Sci 2022 922 46-60
[18]
Wei YL, Li RH, and Yang WH The g-extra edge-connectivity of balanced hypercubes J Interconnect Netw 2021
[19]
Xu LQ and Zhou SM An O(log2(N)) algorithm for reliability assessment of augmented cubes based on h-extra edge-connectivity J Supercomput 2022 78 6739-6751
[20]
Yu ZC, Xu LQ, Yin SS, and Guo LT Super vertex (edge)-connectivity of varietal hypercube Symmetry 2022
[21]
Zhang MZ, Ma WH, and Ma TL Many-to-many disjoint paths in augmented cubes with exponential fault edges IEEE Access 2021 9 95382-95390
[22]
Zhang MZ, Meng JX, Yang WH, and Tian YZ Reliability analysis of bijective connection networks in terms of the extra edge-connectivity Inform Sci 2014 279 374-382
[23]
Zhang MZ, Meng JX, and Yang WH On the extra edge-connectivity of hypercubes Appl Math J Chin Univ 2016 31 198-204
[24]
Zhang MZ, Zhang LZ, Feng X, and Lai HJ An O(log2(N)) algorithm for reliability evaluation of h-extra edge-connectivity of folded hypercubes IEEE Trans Reliab 2018 67 297-307
[25]
Zhang MZ, Zhang LZ, and Feng X Reliability measures in relation to the h-extra edge-connectivity of folded hypercubes Theor Comput Sci 2016 615 71-77
[26]
Zhang MZ Edge isopermetric problem on graphs and the related applications 2018 Xiamen University of Xiamen 68-77
[27]
Zhang QF, Xu LQ, and Yang WH Reliability analysis of the augmented cubes in terms of the extra edge-connectivity and the component edge-connectivity J Parallel Distrib Comput 2021 147 124-131

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Combinatorial Optimization
Journal of Combinatorial Optimization  Volume 47, Issue 2
Mar 2024
326 pages

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 24 January 2024
Accepted: 12 December 2023

Author Tags

  1. h-Extra edge-connectivity
  2. Concentration behavior
  3. Reliability evaluation
  4. Interconnection networks

Qualifiers

  • Research-article

Funding Sources

  • This work was supported by National Natural Science Foundation of China (No.12101528), Science and Technology Project of Xinjiang Uygur Autonomous Region (No. 2020D01C069), Doctoral Startup Foundation of Xinjiang University (No. 62031224736), Tianchi Ph.D

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 0
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Dec 2024

Other Metrics

Citations

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media