完全二部图的线图中的完全独立生成树
Completely Independent Spanning Trees in the Line Graphs of Complete Bipartite Graphs
DOI: 10.12677/aam.2025.142054, PDF,    科研立项经费支持
作者: 赖锦城, 何伟骅*：广东工业大学数学与统计学院，广东 广州
关键词: 完全独立生成树；完全二部图；线图；划分；Completely Independent Spanning Trees； Complete Bipartite Graph； Line Graph； Partition
摘要: 完全独立生成树(CISTs)在计算机网络或通信网络的设计中提供了一个重要的架构选择。对于给定图的多个CISTs的构造，已证明其解决方案的实用性和在实际应用中的优化潜力。文章提出了一种高效的算法，用于在完全二部图的线图中构造CISTs，该算法建立了完全二部图的边划分与其线图的顶点划分之间的关联。此外，还进行了实验测试该算法并验证其正确性。
Abstract: Completely Independent Spanning Trees (CISTs) provide an important architectural choice in the design of computer networks or communication networks. The construction of multiple CISTs for a given graph has demonstrated the practicality of its solutions and optimization potential in real-world applications. This paper proposes an efficient algorithm for constructing CISTs in the line graphs of complete bipartite graphs, which establishes the correlation between the edge partition of the complete bipartite graph and the vertex partition of its line graph. In addition, experiments were conducted to test the performance of the algorithm and to verify its correctness.
文章引用：赖锦城, 何伟骅. 完全二部图的线图中的完全独立生成树[J]. 应用数学进展, 2025, 14(2): 81-92. https://doi.org/10.12677/aam.2025.142054

参考文献

[1] Hasunuma, T. (2001) Completely Independent Spanning Trees in the Underlying Graph of a Line Digraph. Discrete Mathematics, 234, 149-157. [Google Scholar] [CrossRef] 
[2] Hasunuma, T. (2002) Completely Independent Spanning Trees in Maximal Planar Graphs. In: Goos, G., Hartmanis, J., Leeuwen, J. and Kučera, L., Eds., Graph-Theoretic Concepts in Computer Science, Springer, 235-245. [Google Scholar] [CrossRef] 
[3] Lin, W., Li, X.-Y., Chang, J.-M. and Jia, X.H. (2023) Constructing Multiple CISTs on BCube-Based Data Center Networks in the Occurrence of Switch Failures. IEEE Transactions on Computers, 72, 1971-1984. [Google Scholar] [CrossRef] 
[4] Hussain, Z., Al Azemi, F. and Al Bdaiwi, B. (2024) Completely Independent Spanning Trees in Eisenstein-Jacobi Networks. The Journal of Supercomputing, 1-17.
[5] Li, X., Lin, W., Liu, X., Lin, C., Pai, K. and Chang, J. (2022) Completely Independent Spanning Trees on BCCC Data Center Networks with an Application to Fault-Tolerant Routing. IEEE Transactions on Parallel and Distributed Systems, 33, 1939-1952. [Google Scholar] [CrossRef] 
[6] Pai, K., Chang, R. and Chang, J. (2020) A Protection Routing with Secure Mechanism in Möbius Cubes. Journal of Parallel and Distributed Computing, 140, 1-12. [Google Scholar] [CrossRef] 
[7] Pai, K., Chang, R., Wu, R. and Chang, J. (2020) Three Completely Independent Spanning Trees of Crossed Cubes with Application to Secure-Protection Routing. Information Sciences, 541, 516-530. [Google Scholar] [CrossRef] 
[8] Tapolcai, J. (2012) Sufficient Conditions for Protection Routing in IP Networks. Optimization Letters, 7, 723-730. [Google Scholar] [CrossRef] 
[9] Moinet, A., Darties, B., Gastineau, N., Baril, J. and Togni, O. (2017) Completely Independent Spanning Trees for Enhancing the Robustness in Ad-Hoc Networks. 2017 IEEE 13th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), Rome, 9-11 October 2017, 63-70. [Google Scholar] [CrossRef] 
[10] Péterfalvi, F. (2012) Two Counterexamples on Completely Independent Spanning Trees. Discrete Mathematics, 312, 808-810. [Google Scholar] [CrossRef] 
[11] Pai, K., Yang, J., Yao, S., Tang, S. and Chang, J. (2014) Completely Independent Spanning Trees on Some Interconnection Networks. IEICE Transactions on Information and Systems, 97, 2514-2517. [Google Scholar] [CrossRef] 
[12] Cheng, B., Wang, D. and Fan, J. (2017) Constructing Completely Independent Spanning Trees in Crossed Cubes. Discrete Applied Mathematics, 219, 100-109. [Google Scholar] [CrossRef] 
[13] Pai, K., Tang, S., Chang, J. and Yang, J. (2013) Completely Independent Spanning Trees on Complete Graphs, Complete Bipartite Graphs and Complete Tripartite Graphs. In: Chang, R.-S., Jain, L.C. and Peng, S.-L., Eds., Smart Innovation, Systems and Technologies, Springer, 107-113. [Google Scholar] [CrossRef] 
[14] Araki, T. (2013) Dirac’s Condition for Completely Independent Spanning Trees. Journal of Graph Theory, 77, 171-179. [Google Scholar] [CrossRef] 
[15] Li, H., He, W., Yang, W. and Bai, Y. (2015) A Note on Edge-Disjoint Hamilton Cycles in Line Graphs. Graphs and Combinatorics, 32, 741-744. [Google Scholar] [CrossRef] 
[16] Tian, T. and Xiong, L. (2018) Traceability on 2-Connected Line Graphs. Applied Mathematics and Computation, 321, 463-471. [Google Scholar] [CrossRef] 
[17] Dong, F. and Yan, W. (2016) Expression for the Number of Spanning Trees of Line Graphs of Arbitrary Connected Graphs. Journal of Graph Theory, 85, 74-93. [Google Scholar] [CrossRef] 
[18] Li, D. and Wu, J. (2015) On Data Center Network Architectures for Interconnecting Dual-Port Servers. IEEE Transactions on Computers, 64, 3210-3222. [Google Scholar] [CrossRef] 
[19] Wang, X., Fan, J., Lin, C., Zhou, J. and Liu, Z. (2018) BCDC: A High-Performance, Server-Centric Data Center Network. Journal of Computer Science and Technology, 33, 400-416. [Google Scholar] [CrossRef] 
[20] Wang, Y., Cheng, B., Qian, Y. and Wang, D. (2022) Constructing Completely Independent Spanning Trees in a Family of Line-Graph-Based Data Center Networks. IEEE Transactions on Computers, 71, 1194-1203. [Google Scholar] [CrossRef] 
[21] Bian, Q., Cheng, B., Fan, J. and Pan, Z. (2022) Completely Independent Spanning Trees in the Line Graphs of Torus Networks. In: Lai, Y.X., et al., Eds., Algorithms and Architectures for Parallel Processing, Springer International Publishing, 540-553. [Google Scholar] [CrossRef] 

为你推荐