Constructing Two Completely Independent Spanning Trees in Balanced Hypercubes

Yi-Xian YANG  Kung-Jui PAI  Ruay-Shiung CHANG  Jou-Ming CHANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.12   pp.2409-2412
Publication Date: 2019/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019PAL0001
Type of Manuscript: Special Section LETTER (Special Section on Parallel and Distributed Computing and Networking)
Category: Fundamentals of Information Systems
Keyword: 
interconnection networks,  completely independent spanning trees,  balanced hypercubes,  diameter,  

Full Text: PDF(303.2KB)>>
Buy this Article




Summary: 
A set of spanning trees of a graphs G are called completely independent spanning trees (CISTs for short) if for every pair of vertices x, yV(G), the paths joining x and y in any two trees have neither vertex nor edge in common, except x and y. Constructing CISTs has applications on interconnection networks such as fault-tolerant routing and secure message transmission. In this paper, we investigate the problem of constructing two CISTs in the balanced hypercube BHn, which is a hypercube-variant network and is superior to hypercube due to having a smaller diameter. As a result, the diameter of CISTs we constructed equals to 9 for BH2 and 6n-2 for BHn when n≥3.