𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Spanning caterpillars of a hypercube

✍ Scribed by Dvo?�k, Tom�?k; Havel, Ivan; Laborde, Jean-Marie; Mollard, Michel

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
184 KB
Volume
24
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Spanning trees of the hypercube Q n have been recently studied by several authors. In this paper, we construct spanning trees of Q n which are caterpillars and establish quantitative bounds for a caterpillar to span Q n . As a corollary, we disprove a conjecture of Harary and Lewinter on the length of the spine of a caterpillar spanning Q n .

📜 SIMILAR VOLUMES

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