The generalized 4-connectivity of folded Petersen cube networks

Huifen Ge; Shumin Zhang; Chengfu Ye; Rongxia Hao; Huifen Ge; Shumin Zhang; Chengfu Ye; Rongxia Hao

doi:10.3934/math.2022809

AIMS Mathematics

2022, Volume 7, Issue 8: 14718-14737. doi: 10.3934/math.2022809

Previous Article Next Article

Research article

The generalized 4-connectivity of folded Petersen cube networks

1.
School of Computer, Qinghai Normal University, Xining 810008, Qinghai, China
2.
School of Mathematics and Statistics, Qinghai Normal University, Xining 810008, Qinghai, China
3.
Academy of Plateau Science and Sustainability, People's Government of Qinghai Province and Beijing Normal University, China
4.
Department of Mathematics, Beijing Jiaotong University, Beijing 100044, China

Received: 27 April 2022 Revised: 29 May 2022 Accepted: 03 June 2022 Published: 08 June 2022
MSC : 05C05, 05C40, 05C76, 68R10

The generalized $ \ell $-connectivity $ \kappa_{\ell}(G) $ of a graph $ G $ is a generalization of classical connectivity $ \kappa(G) $ with $ \kappa_{2}(G) = \kappa(G) $. It serves to measure the capability of connection for any $ \ell $ vertices. The folded Petersen cube network $ FPQ_{n, k} $ can be used to model the topological structure of a communication-efficient multiprocessor. This paper shows that the generalized 4-connectivity of the folded Petersen cube network $ FPQ_{n, k} $ is $ n+3k-1 $. As a corollary, the generalized 3-connectivity of $ FPQ_{n, k} $ also is obtained and the results on the generalized 4-connectivity of hypercube $ Q_n $ and folded Petersen graph $ FP_k $ can be verified. These conclusions provide a foundation for studying the generalized 4-connectivity of Cartesian product graphs.
- generalized 4-connectivity,
- folded Petersen cube networks,
- Cartesian product
Citation: Huifen Ge, Shumin Zhang, Chengfu Ye, Rongxia Hao. The generalized 4-connectivity of folded Petersen cube networks[J]. AIMS Mathematics, 2022, 7(8): 14718-14737. doi: 10.3934/math.2022809

Related Papers:

Abstract

The generalized $ \ell $-connectivity $ \kappa_{\ell}(G) $ of a graph $ G $ is a generalization of classical connectivity $ \kappa(G) $ with $ \kappa_{2}(G) = \kappa(G) $. It serves to measure the capability of connection for any $ \ell $ vertices. The folded Petersen cube network $ FPQ_{n, k} $ can be used to model the topological structure of a communication-efficient multiprocessor. This paper shows that the generalized 4-connectivity of the folded Petersen cube network $ FPQ_{n, k} $ is $ n+3k-1 $. As a corollary, the generalized 3-connectivity of $ FPQ_{n, k} $ also is obtained and the results on the generalized 4-connectivity of hypercube $ Q_n $ and folded Petersen graph $ FP_k $ can be verified. These conclusions provide a foundation for studying the generalized 4-connectivity of Cartesian product graphs.

References

[1]	B. N. Alhasnawi, B. H. Jasim, B. E. Sedhom, Distributed secondary consensus fault tolerant control method for voltage and frequency restoration and power sharing control in multi-agent microgrid, Int. J. Elec. Power, 133 (2021), 107251. https://doi.org/10.1016/j.ijepes.2021.107251 doi: 10.1016/j.ijepes.2021.107251
[2]	B. N. Alhasnawi, B. H. Jasim, B. E. Sedhom, J. M. Guerrero, Consensus algorithm-based coalition game theory for demand management scheme in smart microgrid, Sustain Cities Soc., 74 (2021), 103248. https://doi.org/10.1016/j.scs.2021.103248 doi: 10.1016/j.scs.2021.103248
[3]	B. N. Alhasnawi, B. H. Jasim, Z. A. S. A. Rahman, J. M. Guerrero, M. D. Esteban, A novel internet of energy based optimal multi-agent control scheme for microgrid including renewable energy resources, Int. J. Environ. Res. Public Health, 18 (2021), 8146. https://doi.org/10.3390/ijerph18158146 doi: 10.3390/ijerph18158146
[4]	B. N. Alhasnawi, B. H. Jasim, B. E. Sedhom, E. Hossain, J. M. Guerrero, A new decentralized control strategy of microgrids in the internet of energy paradigm, Energies, 14 (2021), 2183. https://doi.org/10.3390/en14082183 doi: 10.3390/en14082183
[5]	J. A. Bondy, U. S. R. Murty, Graph theory, New York: Springer, 2008.
[6]	G. Chartrand, S. F. Kapoor, L. Lesniak, D. R. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq., 2 (1984), 1–6.
[7]	G. Chartrand, F. Okamoto, P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks, 55 (2010), 360–367. https://doi.org/10.1002/net.20339 doi: 10.1002/net.20339
[8]	G. Chartrand, R. J. Wilson, The Petersen graph, Graph. Appl., 69 (1985), 100.
[9]	S. K. Das, S. Öhring, A. K. Banejee, Embeddings into hyper {P}etersen networks: Yet another hypercube-like interconnection topology, VLSl Design, 2 (1995), 335–351. https://doi.org/10.1155/1995/95759 doi: 10.1155/1995/95759
[10]	K. Efe, P. K. Blackwell, W. Slough, T. Shiau, Topological properties of the crossed cube architecture, Parallel Comput., 20 (1994), 1763–1775. https://doi.org/10.1016/0167-8191(94)90130-9 doi: 10.1016/0167-8191(94)90130-9
[11]	M. Hager, Pendant tree-connectivity, J. Comb. Theory B, 38 (1985), 179–189. https: //doi.org/10.1016/0095-8956(85)90083-8
[12]	C. F. Li, S. W. Li, S. J. Li, The 4-set tree connectivity of $(n, k)$-star networks, Theor. Comput. Sci., 884 (2020), 81–86. https://doi.org/10.1016/j.tcs.2020.08.004 doi: 10.1016/j.tcs.2020.08.004
[13]	H. Li, X. Li, Y. Sun, The generalized 3-connectivity of {C}artesian product graphs, Discrete Math. Theor., 14 (2012), 1. https://doi.org/10.46298/dmtcs.572 doi: 10.46298/dmtcs.572
[14]	H. Li, Y. Ma, W. Yang, 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 doi: 10.1016/j.amc.2016.10.002
[15]	S. Li, Some topics on generalized connectivity of graphs, Nankai University, 2012.
[16]	S. Li, W. Li, X. Li, The generalized connectivity of complete bipartite graphs, 2010, arXiv: 1012.5710v1.
[17]	S. Li, W. Li, Y. Shi, H. Sun, On minimally 2-connected graphs with generalized connectivity $\kappa_{3} = 2$, J. Comb. Optim., 34 (2017), 141–164. https://doi.org/10.1007/s10878-016-0075-z doi: 10.1007/s10878-016-0075-z
[18]	S. Li, W. Li, X. Li, The generalized connectivity of complete equipartition 3-partite graphs, Bull. Malays. Math. Sci. Soc., 37 (2014), 103–121.
[19]	S. Li, X. Li, Note on the hardness of generalized connectivity, J. Comb. Optim., 24 (2012), 389–396. https://doi.org/10.1007/s10878-011-9399-x doi: 10.1007/s10878-011-9399-x
[20]	S. Li, X. Li, Y. Shi, The minimal size of a graph with generalized connectivity $\kappa_{3} \geq 2$, Australas. J. Comb., 51 (2011), 209–220.
[21]	S. Li, X. Li, W. Zhou, Sharp bounds for the generalized connectivity $\kappa_{3}(G)$, Discrete Math., 310 (2010), 2147–2165. https://doi.org/10.1016/j.disc.2010.04.011 doi: 10.1016/j.disc.2010.04.011
[22]	S. Li, Y. Shi, J. Tu, The generalized 3-connectivity of {C}ayley graphs on symmetric groups generated by trees and cycles, Graph. Combinator., 33 (2017), 1195–1209. https://doi.org/10.1007/s00373-017-1837-9 doi: 10.1007/s00373-017-1837-9
[23]	S. Li, J. Tu, 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 doi: 10.1016/j.amc.2015.11.016
[24]	S. Lin, 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 doi: 10.1016/j.dam.2016.12.003
[25]	X. Li, Y. Mao, Y. Sun, On the generalized (edge-)connectivity of graphs, Australas. J. Comb., 58 (2014), 304–319.
[26]	X. Li, Y. Mao, The generalized 3-connectivity of lexicographic product graphs, Discrete Math. Theor., 16 (2014), 339–354. https://doi.org/10.46298/dmtcs.1266 doi: 10.46298/dmtcs.1266
[27]	X. Li, Y. Mao, Generalized connectivity of graphs, Switzerland: Springer, 2016. https://doi.org/10.1007/978-3-319-33828-6
[28]	S. R. Öhring, S. K. Das, Folded {P}etersen cube networks: new competitors for the hypercubes, IEEE T. Parall. Distr., 7 (1996), 151–168. https://doi.org/10.1109/71.485505 doi: 10.1109/71.485505
[29]	G. Sabidussi, Graphs with given group and given graph theoretical properties, Can. J. Math., 9 (1957), 515–525. https://doi.org/10.4153/CJM-1957-060-7 doi: 10.4153/CJM-1957-060-7
[30]	P. C. Saxena, S. Gupta, J. Rai, A delay optimal coterie on the $k$-dimensional folded {P}etersen graph, J. Parallel Distr. Com., 63 (2003), 1026–1035. https://doi.org/10.1016/S0743-7315(03)00116-3 doi: 10.1016/S0743-7315(03)00116-3
[31]	Y. Sun, S. Zhou, Tree connectivities of {C}aylay graphs on {A}belian groups with small degrees, Bull. Malays. Math. Sci. Soc., 39 (2016), 1673–1685. https://doi.org/10.1007/s40840-015-0147-8 doi: 10.1007/s40840-015-0147-8
[32]	H. Whitney, Congruent graphs and connectivity of graphs, Amer. Math. Soc., 54 (1932), 150–168. https://doi.org/10.2307/2371086 doi: 10.2307/2371086
[33]	S. Zhao, R. 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 doi: 10.1016/j.amc.2018.11.023
[34]	S. Zhao, R. 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 doi: 10.1016/j.dam.2018.05.059
[35]	S. Zhao, R. Hao, E. Cheng, Two kinds of generalized connectivity of dual cubes, Discrete Appl. Math., 257 (2019), 306–316. https://doi.org/10.1016/j.dam.2018.09.025 doi: 10.1016/j.dam.2018.09.025
[36]	S. Zhao, R. Hao, 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 doi: 10.1016/j.dam.2020.09.026
[37]	S. Zhao, R. Hao, J. Wu, The generalized 3-connectivity of some regular networks, J. Parallel Distr. Com., 133 (2019), 18–29. https://doi.org/10.1016/j.jpdc.2019.06.006 doi: 10.1016/j.jpdc.2019.06.006
[38]	S. Zhao, R. Hao, L. Wu, The generalized connectivity of $(n, k)$-bubble-sort graphs, Comput. J., 62 (2019), 1277–1283. https://doi.org/10.1093/comjnl/bxy106 doi: 10.1093/comjnl/bxy106

Reader Comments

Your name:*

Email:*
© 2022 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)