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

The starlike trees which span a hypercube

โœ Scribed by Frank Harary; Martin Lewinter

Publisher
Elsevier Science
Year
1988
Tongue
English
Weight
222 KB
Volume
15
Category
Article
ISSN
0898-1221

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 and only if T is equitable. This extends a result of Nebesky who had made this observation for b = 3.

๐Ÿ“œ SIMILAR VOLUMES

A counter-example to a lemma about embed
A counter-example to a lemma about embedding starlike trees into hypercube
โœ M. Kobeissi; M. Mollard ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 93 KB

In this note, we give a counter-example for a lemma of Harary and Lewinter about partitioning the hypercube with an arbitrary number of vertex-disjoint paths of even length. (~) 2001 Elsevier Science Ltd. All rights reserved.

A spanning tree of the 2m-dimensional hy
A spanning tree of the 2m-dimensional hypercube with maximum number of degree-preserving vertices
โœ Sul-young Choi; Puhua Guan ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 190 KB

For an n-dimensional hypercube Q., the maximum number of degree-preserving vertices in a spanning tree is 2"jn if n = 2" for an integer M. (If n # 2", then the maximum number of degree-preserving vertices in a spanning tree is less than 2"/n.) We also construct a spanning tree of Qzm with maximum nu