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
Koji OBOKATA Yukihiro IWASAKI Feng BAO Yoshihide IGARASHI
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.