For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Independent Spanning Trees of Product Graphs and Their Construction
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/11/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
broadcasts, channel graphs, fault tolerance, independent spanning trees, product graphs,
Full Text: PDF>>
A graph G is called an n-channel graph at vertex r if there are n independent spanning trees rooted at r. A graph G is called an n-channel graph if G is an n-channel graph at every vertex. Independent spanning trees of a graph play an important role in fault-tolerant broadcasting in the graph. In this paper we show that if G1 is an n1-channel graph and G2 is an n2-channel graph, then G1G2 is an (n1 + n2)-channel graph. We prove this fact by a construction of n1+n2 independent spanning trees of G1G2 from n1 independent spanning trees of G1 and n2 independent spanning trees of G2. As an application we describe a fault-tolerant broadcasting scheme along independent spanning trees.