Decomposing the hypercube Qn into n isomorphic edge-disjoint trees

SUNScholar Research Repository

Show simple item record

dc.contributor.author Wagner, Stephan
dc.contributor.author Wild, Marcel
dc.date.accessioned 2012-05-16T11:49:57Z
dc.date.issued 2012-02
dc.identifier.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. en_ZA
dc.identifier.issn 0012-365X (online)
dc.identifier.other doi:10.1016/j.disc.2012.01.033
dc.identifier.uri http://hdl.handle.net/10019.1/20997
dc.description The original publication is available at www.sciencedirect.com en_ZA
dc.description The pre-print of this article can be found at http://hdl.handle.net/10019.1/16108 en_ZA
dc.description.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. en_ZA
dc.format.extent p. 1819-1822 : ill.
dc.language.iso en_ZA en_ZA
dc.publisher Elsevier en_ZA
dc.subject Hypercubes en_ZA
dc.subject Decomposition en_ZA
dc.subject Isomorphic trees en_ZA
dc.subject Edge-disjoint trees en_ZA
dc.title Decomposing the hypercube Qn into n isomorphic edge-disjoint trees en_ZA
dc.type Article en_ZA
dc.description.version Publishers' version en_ZA
dc.rights.holder Elsevier en_ZA
dc.embargo.terms 2050-12-31 en_ZA
dc.embargo.lift 2050-12-31


Files in this item

This item appears in the following Collection(s)

Show simple item record