The generalized 3-connectivity and 4-connectivity of crossed cube

Liu, Heqin ; Cheng, Dongqin 

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 791-811

Résumé

The generalized connectivity, an extension of connectivity, provides a new reference for measuring the fault tolerance of networks. For any connected graph G, let S⊆ V(G) and 2≤|S|≤ V(G); κ_G(S) refers to the maximum number of internally disjoint trees in G connecting S. The generalized k-connectivity of G, κ_k(G), is defined as the minimum value of κ_G(S) over all S⊆ V(G) with |S|=k. The n-dimensional crossed cube CQ_n, as a hypercube-like network, is considered as an attractive alternative to hypercube network because of its many good properties. In this paper, we study the generalized 3-connectivity and the generalized 4-connectivity of CQ_n and obtain κ_3(CQ_n)=κ_4(CQ_n)=n-1, where n≥2.

Détail

Keywords: crossed cube, internally disjoint trees, generalized $k$-connectivity, fault tolerance

Bibliographie

[1] J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer Verlag, London, 2008).

[2] K. Efe, The crossed cube architecture for parallel computation, IEEE Trans. Parallel Distrib. Syst. 3 (1992) 513–524. https://doi.org/10.1109/71.159036

[3] H. Gao, B. Lv and K. Wang, Two lower bounds for generalized 3-connectivity of Cartesian product graphs, Appl. Math. Comput. 338 (2018) 305–313. https://doi.org/10.1016/j.amc.2018.04.007

[4] M. Hager, Pendant tree-connectivity, J. Combin. Theory Ser. B 38 (1985) 179–189. https://doi.org/10.1016/0095-8956(85)90083-8

[5] C.-N. Hung, C.-K. Lin, L.-H. Hsu, E. Cheng and L. Lipták, Strong fault-Hamiltonicity for the crossed cube and its extensions, Parallel Process. Lett. 27 (2017) #1750005. https://doi.org/10.1142/S0129626417500050

[6] P.D. Kulasinghe, Connectivity of the crossed cube, Inform. Process. Lett. 61 (1997) 221–226. https://doi.org/10.1016/S0020-0190(97)00012-4

[7] H. Li, Y. Ma, W. Yang and Y. Wang, The generalized 3-connectivity of graph products, Appl. Math. Comput. 295 (2017) 77–83. https://doi.org/10.1016/j.amc.2016.10.002

[8] S. Li, X. Li and W. Zhou, Sharp bounds for the generalized connectivity \kappa3(G), Discrete. Math. 310 (2010) 2147–2163. https://doi.org/10.1016/j.disc.2010.04.011

[9] S. Li, Y. Shi and J. Tu, The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles, Graph Combin. 33 (2017) 1195–1209. https://doi.org/10.1007/s00373-017-1837-9

[10] S. Li, J. Tu and C. Yu, The generalized 3-connectivity of star graphs and bubble-sort graphs, Appl. Math. Comput. 274 (2016) 41–46. https://doi.org/10.1016/j.amc.2015.11.016

[11] S. Li, Y. Zhao, F. Li and R. Gu, The generalized 3-connectivity of the Mycielskian of a graph, Appl. Math. Comput. 347 (2019) 882–890. https://doi.org/10.1016/j.amc.2018.11.006

[12] 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

[13] Z. Pan and D. Cheng, Structure connectivity and substructure connectivity of the crossed cube, Theoret. Comput. Sci. 824–825 (2020) 67–80. https://doi.org/10.1016/j.tcs.2020.04.014

[14] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150–168. https://doi.org/10.2307/2371086

[15] S. Zhao and R.-X. Hao, The generalized connectivity of alternating group graphs and (n,k)-star graphs, Discrete. Appl. Math. 251 (2018) 310–321. https://doi.org/10.1016/j.dam.2018.05.059

[16] S. 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

[17] S. Zhao, R.-X. Hao and J. Wu, The generalized 3-connectivity of some regular networks, J. Parallel Distrib. Comput. 133 (2019) 18–29. https://doi.org/10.1016/j.jpdc.2019.06.006

[18] 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