# zbMATH — the first resource for mathematics

Embedding a subclass of trees into hypercubes. (English) Zbl 1223.05020
Summary: A long standing conjecture of I. Havel [Čas. Pěst. Mat. 109, 135–152 (1984; Zbl 0544.05057)] states that every equipartite tree with maximum degree 3 on $$2^n$$ vertices is a spanning subgraph of the $$n$$-dimensional hypercube. The conjecture is known to be true for many subclasses of trees. I. Havel and P. Liebl [J. Graph Theory 10, No. 1, 69-77 (1986; Zbl 0589.05031)] showed that every equipartite caterpillar with maximum degree 3 and having $$2^n$$ vertices is a spanning subgraph of the $$n$$-dimensional hypercube. Subsequently, I. Havel [Topics in combinatorics and graph theory. Essays in honour of Gerhard Ringel, 353–358 (1990; Zbl 0743.05016)] remarked that the problem of verification of the conjecture for subdivisions of caterpillars with maximum degree 3 has remained open. In this paper, we show that a subdivision of a caterpillar with $$2^n$$ vertices and maximum degree 3 is a spanning subgraph of the $$n$$-dimensional hypercube if it is equipartite and has at most $$n - 3$$ vertices on the spine. The problem of embedding such trees that have spines of arbitrary length is still open.

##### MSC:
 05C05 Trees 05C65 Hypergraphs 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
##### Keywords:
caterpillar; hypercube; embedding; spanning subgraph
Full Text:
##### References:
 [1] Bezrukov, S.; Monien, B.; Unger, W.; Wechsung, G., Embedding ladders and caterpillars into the hypercube, Discrete applied mathematics, 83, 21-29, (1998) · Zbl 0906.05019 [2] Caha, R.; Koubek, V., Optimal embeddings of generalized ladders into hypercubes, Discrete mathematics, 233, 65-83, (2001) · Zbl 0986.05034 [3] Caha, R.; Koubek, V., Optimal embeddings of odd ladders into hypercubes, Discrete mathematics, 116, 1-2, 73-102, (2002) · Zbl 1005.05016 [4] Choudum, S.A.; Indhumathi, R., Embedding height balanced trees and Fibonacci trees in hypercubes, Journal of applied mathematics and computing, 30, 39-52, (2009) · Zbl 1193.68187 [5] Choudum, S.A.; Indhumathi, R., On embedding subclasses of height-balanced trees in hypercubes, Information sciences, 179, 9, 1333-1347, (2009) · Zbl 1171.68028 [6] Choudum, S.A.; Lavanya, S.; Sunitha, V., Disjoint paths in hypercube with prescribed origins and lengths, International journal of computers, 87, 8, 1692-1708, (2010) · Zbl 1221.05216 [7] Duato, J.; Yalamanchili, S.; Ni, L.M., Interconnection networks: an engineering approach, (2002), Morgan Kaufmann [8] Dvořák, T., Dense sets and embedding binary trees into hypercubes, Discrete applied mathematics, 155, 4, 506-514, (2007) · Zbl 1111.05023 [9] Dvořák, T.; Havel, I.; Laborde, J.M.; Mollard, M., Spanning caterpillars of hypercubes, Journal of graph theory, 24, 9-19, (1997) · Zbl 0865.05034 [10] Havel, I., On Hamilton circuits and spanning trees of hypercubes, C˘asopis pro pe˘stování matematiky, 109, 135-152, (1984) · Zbl 0544.05057 [11] Havel, I., On certain trees in hypercube, (), 353-358 · Zbl 0743.05016 [12] Havel, I.; Liebl, P., One-legged caterpillars span hypercubes, Journal of graph theory, 10, 69-77, (1986) · Zbl 0589.05031 [13] Havel, I.; Morávek, J., $$B$$-valuations of graphs, Czechoslovak mathematical journal, 22, 97, 338-351, (1972) · Zbl 0247.05148 [14] Hsu, Lih-Hsing; Lin, Cheng Kuan, Graph theory and interconnection networks, (2008), Taylor and Francis, Inc. · Zbl 1168.05002 [15] Leighton, F.T., Introduction to parallel algorithms and architectures: arrays, trees, hypercubes, (1992), Morgan Kauffmann San Mateo, CA · Zbl 0743.68007 [16] Nebeský, L., On cubes and dichotomic trees, C˘asopis pro pe˘stování matematiky, 99, 164-167, (1974) · Zbl 0277.05101 [17] Nebeský, L., Embedding $$m$$-quasistars into $$n$$-cubes, Czechoslovak mathematical journal, 38, 705-712, (1988) · Zbl 0677.05021 [18] V. Sunitha, Augmented cube: a new interconnection network, Ph.D. Thesis, Department of Mathematics, IIT, Madras, 2002. [19] Wagner, A.; Corneil, D.G., Embedding trees in a hypercube is NP-complete, SIAM journal on computing, 19, 3, 570-590, (1990) · Zbl 0698.68054 [20] West, D.B., Introduction to graph theory, (1996), Prentice Hall USA · Zbl 0845.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.