脊柱立方体网络中的边不交的生成子图

张洪洋; ZHANG Hongyang; 杨大伟; YANG Dawei; 黄钰衡; HUANG Yuheng; 黄梓维; HUANG Ziwei; 张沈锴; ZHANG Shenkai

doi:10.48014/bcam.20251002002

脊柱立方体网络中的边不交的生成子图

Edge-Disjoint Spanning Subgraphs in Spined Cubes

中国应用数学通报 2025年第3卷第4期页码[30-40] 下载全文[1MB]

摘要

超立方体变形网络在并行计算的高性能互连网络设计中扮演着关键角色。其中, 脊柱立方体网络SQn因其在网络直径方面具备独特优势, 被视作一种高效的拓扑方案而备受关注。可嵌入性是网络设计中的核心考量因素之一。本文聚焦于脊柱立方体网络中边不交生成子图的嵌入问题开展研究。首先, 本文证明了一个n-维脊柱立方体网络SQn当n≥3时是双不交圈覆盖[4,2n-1]-泛圈图, 即对满足4≤ℓ ≤2n-1的任意整数ℓ, 在SQn中存在两条长分别为ℓ和2n-ℓ的不交圈。其次, 本文证明了当n≥6时, SQn中有三条边不交的哈密尔顿圈, 这推广了Yang等人(2023)的一项工作。最后, 本文给出了在SQn中构造两棵完全独立支撑树(CISTs)的方法, 其中当n=5或n≥6时, 它们的直径分别为2n-2和2n-3。这一结果部分改进了Pai和Chang(2016)的一项工作, 其中构造的CISTs的直径为2n-1。本文的研究为脊柱立方体网络具有良好的嵌入特性提供了理论依据。

Abstract

Hypercube variant networks play a pivotal role in designing high-performance interconnection networks for parallel computing. The spined cube SQn , distinguished by its unique advantages in network diameter compared to other hypercube variants, has emerged as a promising candidate for efficient network architectures. Embeddability is one of the core considerations in network design. This paper focuses on the embedding edge-disjoint spanning subgraphs in a spined cube. Firstly, it is proven that SQn with n ≥3 is two-disjoint-cycle-cover [4, 2n-1]-pancyclic, that is, for any integer ℓ satisfying 4≤ℓ ≤2n-1, there exist two disjoint cycles in SQn of lengths ℓ and 2n -ℓ , respectively. Secondly, this paper demonstrates that SQn has three edge-disjoint Hamiltonian cycles (EDHCs) when n ≥6, which extends a previous work given by Yang et al. (2023) . Finally, a method to construct two completely independent spanning trees (CISTs) in SQn isprovided, whose diameters are 2n-2 and 2n-3 for n=5 and n ≥6, respectively. This result partially improves upon a prior work by Pai and Chang (2016) , in which the CISTs have diameters 2n-1. These results establish a theoretical foundation for its superior embedding properties of the spined cube.

DOI

10.48014/bcam.20251002002

文章类型

研究性论文

收稿日期

2025-10-02

接收日期

2025-11-01

出版日期

2025-12-28

关键词

互连网络, 脊柱立方体网络, 哈密尔顿圈, 完全独立支撑树, 双不交圈覆盖

Keywords

Interconnection networks, spined cube, hamiltonian cycles, completely independent spanning trees, two disjoint cycle covers

作者

张洪洋¹, 杨大伟^1,2,*, 黄钰衡¹, 黄梓维¹, 张沈锴¹

Author

ZHANG Hongyang¹, YANG Dawei^1,2,*, HUANG Yuheng¹, HUANG Ziwei¹, ZHANG Shenkai¹

所在单位

1. 北京邮电大数学科学学院, 北京 100876
2. 数学与信息网络教育部重点实验室 (北京邮电大学) , 北京 100876

Company

1. School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China
2. Key Laboratory of Mathematics and Information Networks, Ministry of Education (BUPT) , Beijing 100876, China

浏览量

下载量

基金项目

本项研究得到了国家自然科学基金(12101070,12571370)和北京邮电大学大学生创新创业训练计划项目(202307008)资助。

参考文献

[1] XU J M. Topological Structure and Analysis of Interconnection Networks[M]. Kluwer Academic Publishers, 2001.
[2] ADA R, KAISER T, ROSENFELD M, et al. Disjoint Hamilton cycles in the star graph[J]. Inform. Process. Lett. , 2009, 110: 30-35.
https://doi.org/10.1016/j.ipl.2009.10.001.
[3] BHUYAN L N, AGRAWAL D P. Generalized hypercube and hyperbus structures for a computer network[J]. IEEE Trans. Comput. , 1984, 33: 323-3335.
https://doi.org/10.1109/TC.1984.1676437.
[4] ZHOU W J, FAN J X, JIA X H, et al. The spined cube: A new hypercube variant with smaller diameter[J]. Inform. Process. Lett. , 2011, 111: 561-5675.
https://doi.org/10.1016/j.ipl.2011.03.011.
[5] EFE K. A variation on the hypercube with lower diameter[J]. IEEE Trans. Comput. , 1991, 40: 1312-13165.
https://doi.org/10.1109/12.102840.
[6] YANG X, EVANS D J, MEGSON G M. The locally twisted cubes[J]. Int. J. Comput. Math. , 2005, 82: 401-4135.
https://doi.org/10.1080/0020716042000301752.
[7] AROCKIARAJ M, SHALINI A J, DELAILA J N. Embedding algorithm of spined cube into grid structure and its wirelength computation[J]. Theoret. Comput. Sci. , 2022, 905: 69-865.
https://doi.org/10.1016/j.tcs.2021.12.016.
[8] CHENG G L, ZHU Q, WANG X K. On the reliability and fault tolerance of spined cubes[C]//Proceedings of the 2012 International Conference on Wavelet Analysis and Pattern Recognition. Xian, 2012.
https://doi.org/1109/ICWAPR.2012.6294799.
[9] SATOH K, KANEKO K, HANH P T H, et al. Shortest path routing in spined cubes[C]//2017 6th ICT Inter-national Student Project Conference(ICT-ISPC). Johor, 2017.
https://doi.org/10.1109/ICTISPC.2017.8075349.
[10] YANG D W, XU Z H, FENG Y Q, et al. Symmetric property and edge-disjoint Hamiltonian cycles of the spined cube[J]. Appl. Math. Comput. , 2023, 452: 1280755.
https://doi.org/10.1016/j.amc.2023.128075.
[11] YANG D W, FENG Y Q, KWAK J H, et al. Fault-tolerant edge-bipancyclicity of faulty hypercubes under the conditional-fault model[J]. Inform. Sci. , 2016, 329: 317-3285.
https://doi.org/10.1016/j.ins.2015.09.029.
[12] CHENG D. Embedding mutually edge-disjoint cycles into locally twisted cubes[J]. Theor. Comput. Sci. , 2022, 929: 11-175.
https://doi.org/10.1016/j.tcs.2022.06.027.
[13] LIN T J, HSIEH S Y, JUAN J S T. Embedding cycles and paths in product networks and their applications to multi-processor systems[J]. IEEE Trans. Parallel Distrib. Syst. , 2012, 23(6): 1081-1089.
https://doi.org/10.1109/TPDS.2011.245.
[14] KUNG T L, CHEN H C. Complete cycle embedding in crossed cubes with two-disjoint-cycle-cover pancyclicity[J]. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. , 2015, E98-A(12): 2670-26765.
https://doi.org/10.1587/transfunE98.A.2670.
[15] NIU R, ZHOU S, XU M. Two-disjoint-cycle-cover vertex bipancyclicity of bipartite hypercube-like networks[J]. Theoret. Comput. Sci. , 2023, 947: 1137035.
https://doi.org/10.1016/j.tcs.2023.113703.
[16] KUNG T L, CHEN H C, LIN C H, et al. Three types of two-disjoint-cycle-cover pancyclicity and their applications to cycle embedding in locally twisted cubes[J]. Computer J. , 2021, 64: 27-375.
https://doi.org/10.1093/comjnl/bxz134.
[17] ROWLEY R, BOSE B. Edge-disjoint Hamiltonian cycles in de Bruijn networks[C]//Proc. 6th Distributed Memory Computing Conference, 1991: 707-7095.
https://doi.org/10.1109/DMCC.1991.633359.
[18] HUSSAIN Z A, BOSE B, AL-DHELAAN A. Edge disjoint Hamiltonian cycles in Eisenstein-Jacobi networks[J]. J. Parallel Distrib. Comput. , 2015, 86: 62-705.
https://doi.org/10.1016/j.jpdc.2015.08.003.
[19] PAI K J, WU R Y, PENG S L, et al. Explore all metrics Three edge-disjoint Hamiltonian cycles in crossed cubes with applications to fault-tolerant data broadcasting[J]. J. Supercomput. , 2022, 29: 4126-41455.
https://doi.org/10.1109/HPCCDSSSmartCityDependSys53884.2021.00074
[20] PAI K J. Embedding Three Edge-Disjoint Hamiltonian Cycles into Locally Twisted Cubes[C]//Lecture Notes in Comput. Sci. Computing and Combinatorics: vol. 13025. Tainan, Taiwan, 2021: 367-3745.
https://doi.org/10.1007/9783030895433_31.
[21] LÜ H Z, WU T Z. Edge-disjoint Hamiltonian cycles of balanced hypercubes[J]. Inform. Process. Lett. , 2019, 144: 25-305.
https://doi.org/10.1016/j.ipl.2018.12.004.
[22] HASUNUMA T. Completely independent spanning trees in the underlying graph of a line digraph[J]. Discrete Math. , 2001, 234: 149-1575.
https://doi.org/10.1016/S0012365X(00)003770.
[23] HASUNUMA T. Completely independent spanningtrees in maximal planar graphs[M]//Lecture Notes inComput. Sci. Proc. 28th Int. Workshop on Graph-TheoreticConcepts in Computer Science, WG 2002, 2573: 235-2455.
https://doi.org/10.1007/3540363793_21.
[24] PAI K J, CHANG J M. Improving the diameters ofcompletely independent spanning trees in locally twistedcubes[J]. Inform. Process. Lett. , 2019, 141: 22-245.
https://doi.org/10.1016/j.ipl.2018.09.006.
[25] PAI K J, CHANG J M. Constructing two completelyindependent spanning trees in hypercube-variant networks[J]. Theoret. Comput. Sci. , 2016, 652: 28-375.
https://doi.org/10.1016/j.tcs.2016.08.024.
[26] BONDY J A, MURTY U S R. Graph Theory with Applications[M]. New York: Elsevier North Holland, 1976.
[27] VAIDYA A S, RAO P S N, SHANKAR S R. A class ofhypercube-like networks[C]//Proceedings of the 5thIEEE Symposium on Parallel and Distributed Proceeding(SPDP), 1993: 800-8035.
[28] PARK C D, CHWA K Y. Hamiltonian properties onthe class of hypercube-like networks[J]. Inform. Process. Lett. , 2004, 91(1): 11-175.
https://doi.org/10.1016/j.ipl.2004.03.009.
[29] PARK J H,KIM H C,LIM H S.Fault-hamiltonicity of hypercube-like interconnection networks[C]//Proc.of IEEE International Parallel and Distributed Processing Symposium.Denver,2005.
https://doi.org/10.1109/ IPDPS.2005.223.

引用本文

张洪洋, 杨大伟, 黄钰衡, 等. 脊柱立方体网络中的边不交的生成子图[J]. 中国应用数学通报, 2025, 3(4): 30-40.

Citation

ZHANG Hongyang, YANG Dawei, HUANG Yuheng, et al. Edge-disjoint spanning subgraphs in spined cubes[J]. Bulletin of Chinese Applied Mathematics, 2025, 3(4): 30-40.