Decomposing the hypercube Qn into n isomorphic edge-disjoint trees

Wagner, Stephan; Wild, Marcel

Decomposing the hypercube Qn into n isomorphic edge-disjoint trees

Date

2012-02

Authors

Wagner, Stephan

Wild, Marcel

Publisher

Elsevier

Abstract

The problem of finding edge-disjoint trees in a hypercube arises for example in the context of parallel computing [3]. Independently of applications it is of high aesthetic appeal. The hypercube of dimension n, denoted by Qn, comprises 2n vertices each corresponding to a distinct binary string of length n. Two vertices are adjacent if and only if their corresponding binary strings differ in exactly one position. Since each vertex of Qn has degree n, the number of edges is n2n−1. A variety of decomposability options derive from this fact. In the remainder of the introduction we focus on three of them. The first two have been dealt with before in the literature; the third is the topic of this article.

Description

The original publication is available at www.sciencedirect.com
The pre-print of this article can be found at http://hdl.handle.net/10019.1/16108

Keywords

Hypercubes, Decomposition, Isomorphic trees, Edge-disjoint trees

Citation

Wagner, S. & Wild, M. 2012. Decomposing the hypercube Qn into n isomorphic edge-disjoint trees. Discrete Mathematics, 312(10), 1819-1822, doi:10.1016/j.disc.2012.01.033.