完全二部图的线图中的完全独立生成树  

Completely Independent Spanning Trees in the Line Graphs of Complete Bipartite Graphs

作　　者：赖锦城 何伟骅 

机构地区：[1]广东工业大学数学与统计学院,广东 广州

出　　处：《应用数学进展》2025年第2期81-92,共12页Advances in Applied Mathematics

基　　金：广东省自然科学基金面上项目(2021A1515012047)。

摘　　要：完全独立生成树(CISTs)在计算机网络或通信网络的设计中提供了一个重要的架构选择。对于给定图的多个CISTs的构造,已证明其解决方案的实用性和在实际应用中的优化潜力。文章提出了一种高效的算法,用于在完全二部图的线图中构造CISTs,该算法建立了完全二部图的边划分与其线图的顶点划分之间的关联。此外,还进行了实验测试该算法并验证其正确性。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.

关 键 词：完全独立生成树 完全二部图 线图 划分 

分 类 号：O15[理学—数学]