Decomposing the hypercube Qn into n isomorphic edge-disjoint trees

Simple item page
dc.contributor.authorWagner, Stephan
dc.contributor.authorWild, Marcel
dc.date.accessioned2012-05-16T11:49:57Z
dc.date.issued2012-02
dc.descriptionThe original publication is available at www.sciencedirect.comen_ZA
dc.descriptionThe pre-print of this article can be found at http://hdl.handle.net/10019.1/16108en_ZA
dc.description.abstractThe 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.description.versionPublishers' versionen_ZA
dc.embargo.lift2050-12-31
dc.embargo.terms2050-12-31en_ZA
dc.format.extentp. 1819-1822 : ill.
dc.identifier.citationWagner, 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.issn0012-365X (online)
dc.identifier.otherdoi:10.1016/j.disc.2012.01.033
dc.identifier.urihttp://hdl.handle.net/10019.1/20997
dc.language.isoen_ZAen_ZA
dc.publisherElsevieren_ZA
dc.rights.holderElsevieren_ZA
dc.subjectHypercubesen_ZA
dc.subjectDecompositionen_ZA
dc.subjectIsomorphic treesen_ZA
dc.subjectEdge-disjoint treesen_ZA
dc.titleDecomposing the hypercube Qn into n isomorphic edge-disjoint treesen_ZA
dc.typeArticleen_ZA
Files
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.95 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Research Articles (Mathematical Sciences)