Independent Spanning Trees of Product Graphs and Their Construction

概要

論文の詳細を見る
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 G_1 is an n_1-channel graph and G_2 is an n_2 -channel graph, then G_1 x G_2 is an (n_1 + n_2) -channel graph. We prove this fact by a construction of n_1 + n_2 independent spanning trees of G_1 x G_2 from n_1 independent spanning trees of G_1 and n_2 independent spanning trees of G_2. As an application we describe a fault-tolerant broadcasting scheme along independent spanning trees.
社団法人電子情報通信学会の論文
1996-11-25