Congestion-free embedding of 2(n-k) spanning trees in an arrangement graph

The arrangement graph A(n,k) is not only a generalization of star graph (n - k = 1), but also more flexible. In this investigation, we elucidate the p roblem of embedding of multiple spanning trees in an arrangement graph with the objective of congestion-free. This result is to report how to exploit 2(n - k) edge disjoint spanning trees in an arrangement graph, where each c ongestion-free spanning tree's height is 2k - 1. Our scheme is based on a s ubgraph-partitioning scheme. First, we construct 2(n - k) base spanning tre es in every A(n-k+2.2).Then, we recursively construct 2(n - k) spanning tre es from every A(n-k+22) up to A(n.k) by a bottom-up approach. This is a nea r-optimal result since all of possible edges in the base subarragnement A(n -k+2.2) are fully utilized. (C) 2001 Published by Elsevier Science B.V. All rights reserved.