K. Obokata et al., INDEPENDENT SPANNING-TREES OF PRODUCT GRAPHS AND THEIR CONSTRUCTION, IEICE transactions on fundamentals of electronics, communications and computer science, E79A(11), 1996, pp. 1894-1903
Citations number
8
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
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.