The generalized $ k $-connectivity of conditional recursive networks

Yinkui Li; Yilin Song; Zhuomo An; Yinkui Li; Yilin Song; Zhuomo An

doi:10.3934/math.2026075

AIMS Mathematics

2026, Volume 11, Issue 1: 1807-1819. doi: 10.3934/math.2026075

Previous Article Next Article

Research article Special Issues

The generalized $ k $-connectivity of conditional recursive networks

1.
Department of Mathematics, Qinghai Nationalities University, Xining, Qinghai 810000, China
2.
School of Public Education, Qinghai Vocational and Technical University, Xining, Qinghai 810000, China

Received: 27 September 2025 Revised: 26 December 2025 Accepted: 05 January 2026 Published: 20 January 2026
MSC : 05C05, 05C40

The generalized $ k $-connectivity $ \kappa_k(G) $ of graph $ G $ is defined as the maximum number of internally disjoint Steiner trees in $ G $, which is a generalization of classical connectivity $ \kappa(G) $ of $ G $ just for $ k = 2 $. Conditional recursive networks (CRNs) form a new family of composite networks constructed from complete graphs. In this paper, we determine the generalized $ k $-connectivity of CRNs for $ k = 4 $.
- the generalized connectivity,
- the generalized edge-connectivity,
- conditional recursive networks
Citation: Yinkui Li, Yilin Song, Zhuomo An. The generalized $ k $-connectivity of conditional recursive networks[J]. AIMS Mathematics, 2026, 11(1): 1807-1819. doi: 10.3934/math.2026075

Related Papers:

Abstract

The generalized $ k $-connectivity $ \kappa_k(G) $ of graph $ G $ is defined as the maximum number of internally disjoint Steiner trees in $ G $, which is a generalization of classical connectivity $ \kappa(G) $ of $ G $ just for $ k = 2 $. Conditional recursive networks (CRNs) form a new family of composite networks constructed from complete graphs. In this paper, we determine the generalized $ k $-connectivity of CRNs for $ k = 4 $.

References

[1]	L. W. Beineke, R. J. Wilson, Topics in structural graph theory, Cambrige University Press, 2013.
[2]	A. Bondy, U. S. R. Murty, Graph theory, London: Springer, 2008.
[3]	G. Chartrand, F. Okamoto, P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks, 55 (2010), 360–367. http://doi.org/10.1002/net.20339 doi: 10.1002/net.20339
[4]	R. Gu, X. Li, Y. Shi, The generalized $3$-connectivity of random graphs, Acta Mathematica Sinica, Chinese Series, 57 (2014), 321–330. https://doi.org/10.12386/A2014sxxb0032 doi: 10.12386/A2014sxxb0032
[5]	C. Jin, H.-Y. Zhang, C. Wei, The bounds of generalized $4$-connectivity of alternating group graphs, J. Interconnect. Netw., 21 (2021), 2150011. http://doi.org/10.1142/S0219265921500110 doi: 10.1142/S0219265921500110
[6]	S. Li, W. Li, X. Li, The generalized connectivity of complete bipartite graphs, Ars Combinatoria, 104 (2012), 65–79.
[7]	S. Li, W. Li, X. Li, The generalized connectivity of complete equipartition $3$-partite graphs, Bull. Malays. Math. Sci. Soc., 37 (2014), 103–121.
[8]	S. Li, J. Tu, C. Yu, The generalized $3$-connectivity of star graphs and bubble-sort graphs, Appl. Math. Comput., 274 (2016), 41–46. http://doi.org/10.1016/j.amc.2015.11.016 doi: 10.1016/j.amc.2015.11.016
[9]	X. Li, Y. Mao, Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs, Discrete Appl. Math., 185 (2015), 102–112. http://doi.org/10.1016/j.dam.2014.12.009 doi: 10.1016/j.dam.2014.12.009
[10]	X. Li, Y. Mao, Y. Sun, On the generalized (edge-)connectivity of graphs, Australas. J. Comb., 58 (2014), 304–319.
[11]	Y. Li, Y. Mao, Z. Wang, Z. Wei, Generalized connectivity of some total graphs, Czech. Math. J., 71 (2021), 623–640. http://doi.org/10.21136/CMJ.2021.0287-19 doi: 10.21136/CMJ.2021.0287-19
[12]	Y. Li, L. Wei, Note for the conjecture on the generalized $4$-connectivity of total graphs of the complete bipartite graph, Appl. Math. Comput., 458 (2023), 128225. http://doi.org/10.1016/j.amc.2023.128225 doi: 10.1016/j.amc.2023.128225
[13]	J. Wang, Y. Huang, Z. Ouyang, The generalized $4$-connectivity of godan graphs, arXiv: 2405.15147.
[14]	J. Wang, J. Wu, Z. Ouyang, Y. Huang, The generalized $4$-connectivity of burnt pancake graphs, Discrete Appl. Math., 360 (2025), 93–114. http://doi.org/10.1016/j.dam.2024.08.019 doi: 10.1016/j.dam.2024.08.019
[15]	J. Wang, Z. Zhang, Y. Huang, The generalized $3$-connectivity of burnt pancake graphs and godan graphs, AKCE Int. J. Graphs Comb., 20 (2023), 98–103. http://doi.org/10.1080/09728600.2023.2212293 doi: 10.1080/09728600.2023.2212293
[16]	Y. Wang, B. Cheng, Y. Wang, J. Yu, J. Fan, Strongly Menger connectedness of a class of recursive networks, Comput. J., 67 (2024), 2030–2038. https://doi.org/10.1093/comjnl/bxad121 doi: 10.1093/comjnl/bxad121
[17]	H. Zhang, H. Bian, J. Meng, Reliability evaluation of conditional recursive networks under h-conditional restriction, Appl. Math. Comput., 500 (2025), 129399. https://doi.org/10.1016/j.amc.2025.129399 doi: 10.1016/j.amc.2025.129399
[18]	S.-L. Zhao, J.-M. Chang, H.-Z. Li, The generalized $4$-connectivity of pancake graphs, Discrete Appl. Math., 327 (2023), 77–86. http://doi.org/10.1016/j.dam.2022.11.020 doi: 10.1016/j.dam.2022.11.020
[19]	S.-L. Zhao, R.-X. Hao, The generalized connectivity of alternating group graphs and $(n, k)$-star graphs, Discrete Appl. Math., 251 (2018), 310–321. http://doi.org/10.1016/j.dam.2018.05.059 doi: 10.1016/j.dam.2018.05.059
[20]	S.-L. Zhao, R.-X. Hao, J. Wu, The generalized $4$-connectivity of hierarchical cubic networks, Discrete Appl. Math., 289 (2021), 194–206. http://doi.org/10.1016/j.dam.2020.09.026 doi: 10.1016/j.dam.2020.09.026
[21]	Q. Zhou, H. Liu, B. Cheng, Y. Wang, Y. Han, J. Fan, Fault tolerance of recursive match networks based on $g$-good-neighbor fault pattern, Appl. Math. Comput., 461 (2024), 128318. https://doi.org/10.1016/j.amc.2023.128318 doi: 10.1016/j.amc.2023.128318

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)