Congestion-Free Embeddig of 2( n - k ) Spanning Trees in an Arrangement Graph

Abstract

The arrangement graph An,k is not only a generalization of star graph (n - k =1), but also more flexible. In this investigation, we elucidate the problem 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 congestion-free spanning tree's height is 2k - 1. Our scheme is based on a subgraph-partitioning scheme. First, we construct 2(n - k) base spanning trees in every An-k+2,2. Then, we recursively contruct 2(n - k) spanning trees from every An-k+2,2 up to An,k by a bottm-up approach. This is a near-optimal result since all of possible edges in the base subrrangement An-k+2,2 are fully utilized.