zbMATH — the first resource for mathematics

A note on the cubical dimension of new classes of binary trees. (English) Zbl 1363.05030
Summary: The cubical dimension of a graph \(G\) is the smallest dimension of a hypercube into which \(G\) is embeddable as a subgraph. The conjecture of I. Havel [Čas. Pěst. Mat. 109, 135–152 (1984; Zbl 0544.05057)] claims that the cubical dimension of every balanced binary tree with \(2^n\) vertices, \(n\geq 1\), is \(n\). The 2-rooted complete binary tree of depth \(n\) is obtained from two copies of the complete binary tree of depth \(n\) by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice a 2-rooted complete binary tree and prove that every such balanced tree satisfies the conjecture of Havel.
05C05 Trees
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Full Text: DOI Link
[1] S. Bezrukov, B. Monien, W. Unger, G. Wechsung: Embedding ladders and caterpillars into the hypercube. Discrete Appl. Math. 83 (1998), 21–29. · Zbl 0906.05019
[2] C. -C. Chen, R. -J. Chen: Compact embedding of binary trees into hypercubes. Inf. Process. Lett. 54 (1995), 69–72. · Zbl 1022.68594
[3] S. A. Choudum, S. Lavanya: Embedding a subclass of trees into hypercubes. Discrete Math. 311 (2011), 866–871. · Zbl 1223.05020
[4] S. A. Choudum, I. Raman: Embedding height balanced trees and Fibonacci trees in hypercubes. J. Appl. Math. Comput. 30 (2009), 39–52. · Zbl 1193.68187
[5] T. Dvořák: Dense sets and embedding binary trees into hypercubes. Discrete Appl. Math. 155 (2007), 506–514. · Zbl 1111.05023
[6] V. V. Firsov: On isometric embedding of a graph into a Boolean cube. Kibernetika 1965 (1965), 95–96 (In Russian.); Cybernetics 1 (1965), 112–113.
[7] F. Harary, M. Lewinter, W. Widulski: On two-legged caterpillars which span hypercubes. Congr. Numer. 66 (1988), 103–108. · Zbl 0692.05023
[8] I. Havel: On Hamiltonian circuits and spanning trees of hypercubes. Čas. Pěst. Mat. 109 (1984), 135–152. · Zbl 0544.05057
[9] I. Havel, P. Liebl: Embedding the dichotomic tree into the n-cube. Čas. Pěst. Mat. 97 (1972), 201–205. (In Czech.) · Zbl 0229.05109
[10] I. Havel, J. Morávek: B-valuations of graphs. Czech. Math. J. 22 (1972), 338–351. · Zbl 0247.05148
[11] M. Kobeissi, M. Mollard: Spanning graphs of hypercubes: starlike and double starlike trees. Discrete Math. 244 (2002), 231–239. · Zbl 0992.05032
[12] L. Nebeský: On cubes and dichotomic trees. Čas. Pěst. Mat. 99 (1974), 164–167.
[13] M. Nekri, A. Berrachedi: Two new classes of trees embeddable into hypercubes. RAIRO, Oper. Res. 38 (2004), 295–303. · Zbl 1114.05023
[14] A. Wagner, D. G. Corneil: Embedding trees in a hypercube is NP-complete. SIAM J. Comput. 19 (1990), 570–590. · Zbl 0698.68054
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.