Authors
Citation
T. Dvorak et al., SPANNING CATERPILLARS OF A HYPERCUBE, Journal of graph theory, 24(1), 1997, pp. 9-19
Citations number
11
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
ISSN journal
03649024
Volume
24
Issue
1
Year of publication
1997
Pages
9 - 19
Database
ISI
SICI code
0364-9024(1997)24:1<9:SCOAH>2.0.ZU;2-R
Abstract
Spanning trees of the hypercube Q(n) have been recently studied by sev
eral 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 L
ewinter on the length of the spine of a caterpillar spanning Q(n). (C)
1997 John Wiley & Sons, Inc.