# A note on the cubical dimension of new classes of binary trees

Kamal Kabyl; Abdelhafid Berrachedi; Éric Sopena

Czechoslovak Mathematical Journal (2015)

- Volume: 65, Issue: 1, page 151-160
- ISSN: 0011-4642

## Access Full Article

top## Abstract

top## How to cite

topKabyl, Kamal, Berrachedi, Abdelhafid, and Sopena, Éric. "A note on the cubical dimension of new classes of binary trees." Czechoslovak Mathematical Journal 65.1 (2015): 151-160. <http://eudml.org/doc/270054>.

@article{Kabyl2015,

abstract = {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\ge 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.},

author = {Kabyl, Kamal, Berrachedi, Abdelhafid, Sopena, Éric},

journal = {Czechoslovak Mathematical Journal},

keywords = {cubical dimension; embedding; Havel's conjecture; hypercube; tree},

language = {eng},

number = {1},

pages = {151-160},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {A note on the cubical dimension of new classes of binary trees},

url = {http://eudml.org/doc/270054},

volume = {65},

year = {2015},

}

TY - JOUR

AU - Kabyl, Kamal

AU - Berrachedi, Abdelhafid

AU - Sopena, Éric

TI - A note on the cubical dimension of new classes of binary trees

JO - Czechoslovak Mathematical Journal

PY - 2015

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 65

IS - 1

SP - 151

EP - 160

AB - 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\ge 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.

LA - eng

KW - cubical dimension; embedding; Havel's conjecture; hypercube; tree

UR - http://eudml.org/doc/270054

ER -

## References

top- Bezrukov, S., Monien, B., Unger, W., Wechsung, G., 10.1016/S0166-218X(97)00101-7, Discrete Appl. Math. 83 (1998), 21-29. (1998) Zbl0906.05019MR1622961DOI10.1016/S0166-218X(97)00101-7
- Chen, C.-C., Chen, R.-J., 10.1016/0020-0190(95)00010-A, Inf. Process. Lett. 54 (1995), 69-72. (1995) Zbl1022.68594MR1332424DOI10.1016/0020-0190(95)00010-A
- Choudum, S. A., Lavanya, S., 10.1016/j.disc.2011.02.011, Discrete Math. 311 (2011), 866-871. (2011) Zbl1223.05020MR2781631DOI10.1016/j.disc.2011.02.011
- Choudum, S. A., Raman, I., 10.1007/s12190-008-0155-z, J. Appl. Math. Comput. 30 (2009), 39-52. (2009) Zbl1193.68187MR2496600DOI10.1007/s12190-008-0155-z
- Dvořák, T., 10.1016/j.dam.2006.09.003, Discrete Appl. Math. 155 (2007), 506-514. (2007) Zbl1111.05023MR2296871DOI10.1016/j.dam.2006.09.003
- Firsov, V. V., 10.1007/BF01074705, Kibernetika 1965 Russian (1965), 95-96 Cybernetics 1 (1965), 112-113. (1965) MR0210614DOI10.1007/BF01074705
- Harary, F., Lewinter, M., Widulski, W., On two-legged caterpillars which span hypercubes, Congr. Numer. 66 (1988), 103-108. (1988) Zbl0692.05023MR0992892
- Havel, I., On Hamiltonian circuits and spanning trees of hypercubes, Čas. Pěst. Mat. 109 (1984), 135-152. (1984) Zbl0544.05057MR0744871
- Havel, I., Liebl, P., Embedding the dichotomic tree into the $n$-cube, Čas. Pěst. Mat. 97 Czech (1972), 201-205. (1972) Zbl0229.05109MR0306025
- Havel, I., Morávek, J., $B$-valuations of graphs, Czech. Math. J. 22 (1972), 338-351. (1972) Zbl0247.05148MR0294159
- Kobeissi, M., Mollard, M., 10.1016/S0012-365X(01)00086-3, Discrete Math. 244 (2002), 231-239. (2002) Zbl0992.05032MR1844035DOI10.1016/S0012-365X(01)00086-3
- Nebeský, L., On cubes and dichotomic trees, Čas. Pěst. Mat. 99 (1974), 164-167. (1974) Zbl0277.05101MR0354425
- Nekri, M., Berrachedi, A., 10.1051/ro:2004027, RAIRO, Oper. Res. 38 (2004), 295-303. (2004) Zbl1114.05023MR2178082DOI10.1051/ro:2004027
- Wagner, A., Corneil, D. G., 10.1137/0219038, SIAM J. Comput. 19 (1990), 570-590. (1990) Zbl0698.68054MR1041546DOI10.1137/0219038

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.