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 inde pendent spanning trees rooted at r. A graph G is called an n-channel g raph if G in 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 g raph 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 sp anning trees of G(1) and n(2) independent spanning trees of G(2). As a n application we describe a fault-tolerant broadcasting scheme along i ndependent spanning trees.