Article in volume
Authors:
Title:
The generalized 4-connectivity of balanced hypercubes
PDFSource:
Discussiones Mathematicae Graph Theory 44(3) (2024) 1079-1106
Received: 2022-11-11 , Revised: 2023-02-06 , Accepted: 2023-02-07 , Available online: 2023-03-10 , https://doi.org/10.7151/dmgt.2490
Abstract:
The balanced hypercube is a kind of highly symmetrical network and possesses
many good properties. Generalized connectivity is a new measurement of
interconnection networks' fault tolerance. The internally disjoint $N$-trees
are edge-disjoint trees but with intersecting vertex set $N$. Let $\kappa(N)$
be the maximum number of internally disjoint $N$-trees and the generalized
$k$-connectivity of $G$ be $\kappa_k(G)=\min\{\kappa(N) | N \subset V(G)$
and $\vert N \vert=k\}$. In this paper, we study the $n$-dimensional balanced
hypercube $BH_n$ and demonstrate that $\kappa_4(BH_n)=2n-1$ for $n \ge 1$.
Keywords:
interconnection network, balanced hypercube, generalized connectivity, fault tolerance
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory, in: Grad. Texts in Math. 244 (Springer, New York, 2008).
- G. Chartrand, S.F. Kapoor, L. Lesniak and D.R. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2 (1984) 1–6.
- D. Cheng, R.-X. Hao and Y.-Q. Feng, Two node-disjoint paths in balanced hypercubes, Appl. Math. Comput. 242 (2014) 127–142.
https://doi.org/10.1016/j.amc.2014.05.037 - D. Cheng, The $h$-restricted connectivity of balanced hypercubes, Discrete Appl. Math. 305 (2021) 133–141.
https://doi.org/10.1016/j.dam.2021.08.036 - D. Du and X. Hu, Steiner Tree Problem in Computer Communication Networks (World Scientific, Singapore, 2008).
https://doi.org/10.1142/6729 - S. Li, X. Li and W. Zhou, Sharp bounds for the generalized connectivity $\kappa_3(G)$, Discrete Math. 310 (2010) 2147–2163.
https://doi.org/10.1016/j.disc.2010.04.011 - S. Li, Some Topics on Generalized Connectivity of Graphs, Ph.D. Thesis (Nankai University, 2012).
- L. Li, X. Zhang, Q. Zhu and Y. Bai, The $3$-extra conditional diagnosability of balanced hypercubes under MM* model, Discrete Appl. Math. 309 (2022) 310–316.
https://doi.org/10.1016/j.dam.2021.04.004 - C. Li, S. Lin and S. Li, The $4$-set tree connectivity of $(n, k)$-star networks, Theoret. Comput. Sci. 844 (2020) 81–86.
https://doi.org/10.1016/j.tcs.2020.08.004 - S. Lin and Q. Zhang, The generalized $4$-connectivity of hypercubes, Discrete Appl. Math. 220 (2017) 60–67.
https://doi.org/10.1016/j.dam.2016.12.003 - H. Liu and D. Cheng, The generalized $3$-connectivity and $4$-connectivity of crossed cube, Discuss. Math. Graph Theory(2022), in press.
https://doi.org/10.7151/dmgt.2474 - H. Liu and D. Cheng, The generalized $4$-connectivity of folded hypercube, Int. J. Comput. Math. Comput. Syst. Theory 7(4) (2022) 235–245.
https://doi.org/10.1080/23799927.2022.2123405 - H. Liu and D. Cheng, Structure fault tolerance of balanced hypercubes, Theoret. Comput. Sci. 845 (2020) 198–207.
https://doi.org/10.1016/j.tcs.2020.09.015 - H. Lü and H. Zhang, Hyper-Hamiltonian laceability of balanced hypercubes, J. Supercomput. 68 (2014) 302–314.
https://doi.org/10.1007/s11227-013-1040-6 - H. Lü and T. Wu, Edge-disjoint Hamiltonian cycles of balanced hypercubes, Inform. Process. Lett. 144 (2019) 25–30.
https://doi.org/10.1016/j.ipl.2018.12.004 - Y. Saad and M.H. Schultz, Topological properties of hypercubes, IEEE Trans. Comput. 37 (1988) 867–872.
https://doi.org/10.1109/12.2234 - C. Wei, R.-X. Hao and J.-M. Chang, The reliability analysis based on the generalized connectivity in balanced hypercubes, Discrete Appl. Math. 292 (2021) 19–32.
https://doi.org/10.1016/j.dam.2020.12.011 - C. Wei, R.-X. Hao and J.-M. Chang, Two-disjoint-cycle-cover bipancyclicity of balanced hypercubes, Appl. Math. Comput. 381 (2020) 125305.
https://doi.org/10.1016/j.amc.2020.125305 - J. Wu and K. Huang, The balanced hypercube: a cube-based system for fault-tolerant applications, IEEE Trans. Comput. 46 (1997) 484–490.
https://doi.org/10.1109/12.588063 - M. Xu, X.-D. Hu and J.-M. Xu, Edge-pancyclicity and Hamiltonian laceability of the balanced hypercubes, Appl. Math. Comput. 189 (2007) 1393–1401.
https://doi.org/10.1016/j.amc.2006.12.036 - M. Xu and Y. Wei, The $h$-edge tolerable diagnosability of balanced hypercubes, Theoret. Comput. Sci. 795 (2019) 540–546.
https://doi.org/10.1016/j.tcs.2019.08.007 - M.-C. Yang, Conditional diagnosability of balanced hypercubes under the PMC model, Inform. Sci. 222 (2013) 754–760.
https://doi.org/10.1016/j.ins.2012.08.014 - Y. Yang and L. Zhang, Fault-tolerant-prescribed hamiltonian laceability of balanced hypercubes, Inform. Process. Lett. 145 (2019) 11–15.
https://doi.org/10.1016/j.ipl.2019.01.002 - S.-L. Zhao and R.-X. Hao, The generalized $4$-connectivity of exchanged hypercubes, Appl. Math. Comput. 347 (2019) 342–353.
https://doi.org/10.1016/j.amc.2018.11.023 - S.-L. Zhao, R.-X. Hao and J. Wu, The generalized $4$-connectivity of hierarchical cubic networks, Discrete Appl. Math. 289 (2021) 194–206.
https://doi.org/10.1016/j.dam.2020.09.026 - S-L. Zhao and J.-M. Chang, Reliability assessment of the divide-and-swap cube in terms of generalized connectivity, Theoret. Comput. Sci. 943 (2023) 1–15.
https://doi.org/10.1016/j.tcs.2022.12.005 - S.-L. Zhao, J.-M. Chang and H.-Z. Li, The generalized $4$-connectivity of pancake graphs, Discrete Appl. Math. 327 (2023) 77–86.
https://doi.org/10.1016/j.dam.2022.11.020 - J.-X. Zhou, Z.-L. Wu, S.-C. Yang and K.-W. Yuan, Symmetric property and reliability of balanced hypercube, IEEE Trans. Comput. 64 (2015) 876–881.
https://doi.org/10.1109/TC.2014.2304391
Close