- 會議論文
- OpenAccess
How Many Optimal Independent Spanning Trees are there in a Hypercube
摘要
Suppose multiple spanning trees rooted at same vertex r in a graph. They are mutually independent if for each non-root vertex v, paths from v to r, one path in each spanning trees, are internally disjoint and no common edge. It has been proved that there exist n optimal independent spanning trees (OIST for short) rooted at any vertex in the n-dimensional hypercube (denoted by Q_n). The optimal requirement is achieved when the distance from v to the only child of r is the Hamming distance in every spanning tree. In this paper, the number of OIST solutions in Q_n is concerned. A routing square is an n by n matrix, which can represent an OIST solution, but not every OIST solution has a correspondent routing square. Let R_n denote the number of routing squares of Q_n and let f(m) denote the number of m 1-bits vertices in Q_n. An upper bound and a lower bound for the number of OIST solutions in Q_n are proved to be II^n _(m=3) (!m)^(f(m)) and R_n, respectively, where !m is the derangement number of m.