Independent Spanning Trees of 2-Chordal Rings

Yukihiro HAMADA

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A    No.1    pp.355-362
Publication Date: 2016/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.355
Type of Manuscript: PAPER
Category: Graphs and Networks
k-chordal ring,  connectivity,  independent spanning trees,  fault-tolerant broadcasting,  secure message distribution,  

Full Text: PDF>>
Buy this Article

Two spanning trees T1,T2 of a graph G = (V,E) are independent if they are rooted at the same vertex, say r, and for each vertex vV, the path from r to v in T1 and the path from r to v in T2 have no common vertices and no common edges except for r and v. In general, spanning trees T1,T2,…,Tk of a graph G = (V,E) are independent if they are pairwise independent. A graph G = (V,E) is called a 2-chordal ring and denoted by CR(N,d1,d2), if V = {0,1,…,N-1} and E = {(u,v)|[v-u]N = 1 or [v-u]N = d1 or [v-u]N = d2, 2 ≤ d1 < d2N/2}. CR(N,d1,N/2) is 5-connected if N ≥ 8 is even and d1N/2-1. We give an algorithm to construct 5 independent spanning trees of CR(N,d1,N/2),N ≥ 8 is even and 2 ≤ d1 ≤ ⌈N/4⌉.