Yali Sun ; Mingzu Zhang ; Xing Feng ; Xing Yang - A concentration phenomenon for $h$-extra edge-connectivity reliability analysis of enhanced hypercubes $Q_{n,2}$ with exponentially many faulty links

fi:13487 - Fundamenta Informaticae, October 26, 2025, Volume 194, Issue 1 - https://doi.org/10.46298/fi.13487
A concentration phenomenon for $h$-extra edge-connectivity reliability analysis of enhanced hypercubes $Q_{n,2}$ with exponentially many faulty linksArticle

Authors: Yali Sun ; Mingzu Zhang ; Xing Feng ; Xing Yang

    Reliability assessment of interconnection networks is critical to the design and maintenance of multiprocessor systems. The $(n, k)$-enhanced hypercube $Q_{n,k}$, as a variation of the hypercube $Q_{n}$, was proposed by Tzeng and Wei in 1991. As an extension of traditional edge-connectivity, $h$-extra edge-connectivity of a connected graph $G,$ $λ_h(G),$ is an essential parameter for evaluating the reliability of interconnection networks. This article intends to study the $h$-extra edge-connectivity of the $(n,2)$-enhanced hypercube $Q_{n,2}$. Suppose that the link malfunction of an interconnection network $Q_{n,2}$ does not isolate any subnetwork with no more than $h-1$ processors, the minimum number of these possible faulty links concentrates on a constant $2^{n-1}$ for each integer $\lceil\frac{11\times2^{n-1}}{48}\rceil \leq h \leq 2^{n-1}$ and $n\geq 9$. That is, for about $77.083\%$ of values where $h\leq2^{n-1},$ the corresponding $h$-extra edge-connectivity of $Q_{n,2}$, $λ_h(Q_{n,2})$, presents a concentration phenomenon. Moreover, the lower and upper bounds of $h$ mentioned above are both tight.


    Volume: Volume 194, Issue 1
    Published on: October 26, 2025
    Accepted on: November 11, 2024
    Submitted on: April 29, 2024
    Keywords: Combinatorics, Discrete Mathematics

    Publications

    References
    Sun, Y., Zhang, M., Feng, X., & Yang, X. (2024). A concentration phenomenon for $h$-extra edge-connectivity reliability analysis of enhanced hypercubes Q_{n,2} with exponentially many faulty links (Versions 2). arXiv. 10.48550/ARXIV.2404.17150

    Consultation statistics

    This page has been seen 51 times.
    This article's PDF has been downloaded 23 times.