Constructing edge-disjoint spanning trees in product networks

A Cartesian product network is obtained by applying the cross operation on two graphs. In this paper, we study the problem of constructing the maximum number of edge-disjoint spanning trees (abbreviated to EDSTs) in Cartesian product networks. Let G = (V-G, E-G) be a graph having n(1) EDSTs and F = (V-F, E-F) be a graph having n(2) EDSTs. Two methods are proposed for constructing EDSTs in the Cartesian product of G and F, denoted by G x F. The graph G has t(1) \E-G\ - n(1)(\V-G\ - 1) more edges than that are necessary for constructing n(1) EDSTs in it, and the graph F has t(2) = \E-F\ - n(2)(\V-F\ - 1) more edges than that are necessary for constructing n(2) EDSTs in it. By assuming that t(1) > n(1) and t(2) > n(2), our first construction shows that n(1) + n(2) EDSTs can be constructed in G x F. Our second construction does not need any assumption and it constructs n(1) + n(2) - 1 EDSTs in G x F. By applying the proposed methods, it is easy to construct the maximum numbers of EDSTs in many important Cartesian product networks, such as hypercubes, tori, generalized hypercubes, mesh connected trees, and hyper Petersen networks.