๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Leafy spanning trees in hypercubes

โœ Scribed by W. Duckworth; P.E. Dunne; A.M. Gibbons; M. Zito

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
214 KB
Volume
14
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

โœฆ Synopsis

We prove that the d-dimensional hypercube, Qd, with n ----2 d vertices, contains a spanning tree with at least 1 log 2 n o n -t-2 leaves. This improves upon the bound implied by a more general result on spanning trees in graphs with minimum degree 5, which gives (1 -O(loglogn)/log 2 n)n as a lower bound on the maximum number of leaves in spanning trees of n-vertex hypercubes. (~) 2001 Elsevier Science Ltd. All rights reserved.

๐Ÿ“œ SIMILAR VOLUMES

Hierarchical spanning trees and distribu
Hierarchical spanning trees and distributing on incomplete hypercubes
โœ Jenn-Yang Tien; Wei-Pang Yang ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 873 KB

Tien, J.-Y. and W.-P. Yang, Hierarchical spanning trees and distributing on incomplete hypercubes, Parallel Computing 17 (1991) 1343-1360\_ Incomplete hypercubes are gaining increasing attention as one of the possible solutions for the limitation on the number of nodes in the hypercubes. Distributi

Parallel construction of optimal indepen
Parallel construction of optimal independent spanning trees on hypercubes
โœ Jinn-Shyong Yang; Shyue-Ming Tang; Jou-Ming Chang; Yue-Li Wang ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 212 KB

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and bandwidth. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Tang et al. [S.-M. Tang,

The starlike trees which span a hypercub
The starlike trees which span a hypercube
โœ Frank Harary; Martin Lewinter ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 222 KB

A connected bipartite graph is called equitable if it has the same number of nodes in each of its two colors. A starlike tree with b branches is a subdivision of the star K~. b with b ~> 3. We prove that a starlike tree T with b branches, where 3 ~< b ~< n, having 2 n nodes spans the hypercube Qn if