Decomposing the hypercube Qn into n isomorphic edge-disjoint trees

被引：11
作者：
Wagner, Stephan [1 ]
Wild, Marcel [1 ]
机构：
[1] Univ Stellenbosch, Dept Math Sci, ZA-7602 Matieland, South Africa
来源：
DISCRETE MATHEMATICS | 2012年 / 312卷 / 10期
关键词：
Hypercube; Decomposition; Isomorphic trees; SPANNING-TREES;
D O I：
10.1016/j.disc.2012.01.033
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that the edge set of the n-dimensional hypercube Q(n) is the disjoint union of the edge sets of n isomorphic trees. (c) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码：1819 / 1822
页数：4
相关论文
共 9 条
[1]   On edge-disjoint spanning trees in hypercubes [J].
Barden, B ;
Libeskind-Hadas, R ;
Davis, J ;
Williams, W .
INFORMATION PROCESSING LETTERS, 1999, 70 (01) :13-16
[2]   ON THE DECOMPOSITION OF N-CUBES INTO ISOMORPHIC TREES [J].
FINK, JF .
JOURNAL OF GRAPH THEORY, 1990, 14 (04) :405-411
[3]  
Leighton F.T., 1992, Introduction to Parallel Algorithms and Architechtures: Arrays, Trees, Hypercubes
[4]   On the spanning tree packing number of a graph: a survey [J].
Palmer, EM .
DISCRETE MATHEMATICS, 2001, 230 (1-3) :13-21
[5]  
Ramras M, 1997, ARS COMBINATORIA, V46, P3
[6]   SYMMETRICAL EDGE-DECOMPOSITIONS OF HYPERCUBES [J].
RAMRAS, M .
GRAPHS AND COMBINATORICS, 1991, 7 (01) :65-87
[7]   A NOTE ON FINDING MINIMUM-COST EDGE-DISJOINT SPANNING-TREES [J].
ROSKIND, J ;
TARJAN, RE .
MATHEMATICS OF OPERATIONS RESEARCH, 1985, 10 (04) :701-708
[8]  
Rymon R, 1992, SEARCH SYSTEMATIC SE
[9]   COVER-PRESERVING ORDER EMBEDDINGS INTO BOOLEAN LATTICES [J].
WILD, M .
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1992, 9 (03) :209-232
1