An Algorithm to Construct Completely Independent Spanning Trees in Line Graphs. (13th September 2021)

• Record Type: Journal Article
• Authors: Wang, Yifeng; Cheng, Baolei; Fan, Jianxi; Qian, Yu; Jiang, Ruofan
• Is Part Of: Computer journal. Volume 65:Number 12(2022)
• Page Start: 2979
• Page End: 2990
• Publication Date: 2021-09-13
• Subjects: completely independent spanning trees -- internally disjoint paths -- line graph -- interconnection network; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxab120
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: In the past few years, much importance and attention have been attached to completely independent spanning trees (CISTs). Many results, such as edge-disjoint Hamilton cycles, traceability, number of spanning trees, structural properties, topological indices, etc., have been obtained on line graphs, and researchers have applied the line graphs of some interconnection networks such as generalized hypercubes, augmented cubes, crossed cubes, etc., into data center networks, such as SWCube, AQLCube, BCDC, etc. At the meanwhile, few results of CISTs are reported on the line graphs. In this paper, we establish the relation of edge-disjoint spanning trees in an interconnection network $G$ ' with its line graph $G$ by proposing a general algorithm for the first time. By this method, more CISTs can be obtained comparing with results in the literature. Then, the decrease of diameter is discussed and simulation experiments are shown on the line graphs of hypercubes.