Constructing edge-disjoint spanning trees on product networks

[[abstract]]Abstract澤 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. LetG=(V_G, E_G)be a graph havingn_1EDSTs andF=(V_F, E_F)be a graph havingn_2EDSTs. Two methods are proposed for constructing EDSTs in the Cartesian product ofGandF , denoted byG\times F . The graphGhast_1=|E_G|-n_1(|V_G|-1)more edges than that are necessary for constructingn_1EDSTs in it, and the graphFhast_2=|E_F|-n_2(|V_F|-1)more edges than that are necessary for constructingn_2EDSTs in it. By assuming thatt_1\ge n_1andt_2 \ge n_2 , our first construction shows thatn_1+ n_2EDSTs can be constructed inG \times F . Our second construction does not need any assumption and it constructsn_1 + n_2-1EDSTs inG \times 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.[[department]]資訊工程學