Article in volume
Authors:
Heqin H. Liu
Department of Mathematics
College of Information Science and Technology / College of Cyberspace Security
Jinan University
Guangzhou 510632, China
email: 2651455238@qq.com
Title:
The generalized 3-connectivity and 4-connectivity of crossed cube
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 791-811
Received: 2022-06-11 , Revised: 2022-09-01 , Accepted: 2022-09-01 , Available online: 2022-10-19 , https://doi.org/10.7151/dmgt.2474
Abstract:
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\subseteq V(G)$ and $2\le|S|\le V(G)$; $\kappa_G(S)$ refers to the
maximum number of internally disjoint trees in $G$ connecting $S$.
The generalized $k$-connectivity of $G$, $\kappa_k(G)$, is defined as the
minimum value of $\kappa_G(S)$ over all $S\subseteq 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
$\kappa_3(CQ_n)=\kappa_4(CQ_n)=n-1$, where $n\ge2$.
Keywords:
crossed cube, internally disjoint trees, generalized $k$-connectivity, fault tolerance
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer Verlag, London, 2008).
- 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 - 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 - M. Hager, Pendant tree-connectivity, J. Combin. Theory Ser. B 38 (1985) 179–189.
https://doi.org/10.1016/0095-8956(85)90083-8 - 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 - 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 - 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 - 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, 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 - 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 - 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 - 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 - 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 - H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150–168.
https://doi.org/10.2307/2371086 - 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 - 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 - 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 - 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
Close