Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
cubical dimension; embedding; Havel's conjecture; hypercube; tree
cubical dimension; embedding; Havel's conjecture; hypercube; tree
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 Havel (1984) 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.
References:
[1] Bezrukov, S., Monien, B., Unger, W., Wechsung, G.: Embedding ladders and caterpillars into the hypercube. Discrete Appl. Math. 83 (1998), 21-29. DOI 10.1016/S0166-218X(97)00101-7 | MR 1622961 | Zbl 0906.05019
[2] Chen, C.-C., Chen, R.-J.: Compact embedding of binary trees into hypercubes. Inf. Process. Lett. 54 (1995), 69-72. DOI 10.1016/0020-0190(95)00010-A | MR 1332424 | Zbl 1022.68594
[3] Choudum, S. A., Lavanya, S.: Embedding a subclass of trees into hypercubes. Discrete Math. 311 (2011), 866-871. DOI 10.1016/j.disc.2011.02.011 | MR 2781631 | Zbl 1223.05020
[4] Choudum, S. A., Raman, I.: Embedding height balanced trees and Fibonacci trees in hypercubes. J. Appl. Math. Comput. 30 (2009), 39-52. DOI 10.1007/s12190-008-0155-z | MR 2496600 | Zbl 1193.68187
[5] Dvořák, T.: Dense sets and embedding binary trees into hypercubes. Discrete Appl. Math. 155 (2007), 506-514. DOI 10.1016/j.dam.2006.09.003 | MR 2296871 | Zbl 1111.05023
[6] Firsov, V. V.: On isometric embedding of a graph into a Boolean cube. Kibernetika 1965 Russian (1965), 95-96 Cybernetics 1 (1965), 112-113. DOI 10.1007/BF01074705 | MR 0210614
[7] Harary, F., Lewinter, M., Widulski, W.: On two-legged caterpillars which span hypercubes. Congr. Numer. 66 (1988), 103-108. MR 0992892 | Zbl 0692.05023
[8] Havel, I.: On Hamiltonian circuits and spanning trees of hypercubes. Čas. Pěst. Mat. 109 (1984), 135-152. MR 0744871 | Zbl 0544.05057
[9] Havel, I., Liebl, P.: Embedding the dichotomic tree into the $n$-cube. Čas. Pěst. Mat. 97 Czech (1972), 201-205. MR 0306025 | Zbl 0229.05109
[10] Havel, I., Morávek, J.: {$B$}-valuations of graphs. Czech. Math. J. 22 (1972), 338-351. MR 0294159 | Zbl 0247.05148
[11] Kobeissi, M., Mollard, M.: Spanning graphs of hypercubes: starlike and double starlike trees. Discrete Math. 244 (2002), 231-239. DOI 10.1016/S0012-365X(01)00086-3 | MR 1844035 | Zbl 0992.05032
[12] Nebeský, L.: On cubes and dichotomic trees. Čas. Pěst. Mat. 99 (1974), 164-167. MR 0354425 | Zbl 0277.05101
[13] Nekri, M., Berrachedi, A.: Two new classes of trees embeddable into hypercubes. RAIRO, Oper. Res. 38 (2004), 295-303. DOI 10.1051/ro:2004027 | MR 2178082 | Zbl 1114.05023
[14] Wagner, A., Corneil, D. G.: Embedding trees in a hypercube is NP-complete. SIAM J. Comput. 19 (1990), 570-590. DOI 10.1137/0219038 | MR 1041546 | Zbl 0698.68054
Search
Partner of
