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

Abstract

top
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 ≥ 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.

How to cite

top

Kabyl, 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
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. Firsov, V. V., 10.1007/BF01074705, Kibernetika 1965 Russian (1965), 95-96 Cybernetics 1 (1965), 112-113. (1965) MR0210614DOI10.1007/BF01074705
  7. Harary, F., Lewinter, M., Widulski, W., On two-legged caterpillars which span hypercubes, Congr. Numer. 66 (1988), 103-108. (1988) Zbl0692.05023MR0992892
  8. Havel, I., On Hamiltonian circuits and spanning trees of hypercubes, Čas. Pěst. Mat. 109 (1984), 135-152. (1984) Zbl0544.05057MR0744871
  9. Havel, I., Liebl, P., Embedding the dichotomic tree into the n -cube, Čas. Pěst. Mat. 97 Czech (1972), 201-205. (1972) Zbl0229.05109MR0306025
  10. Havel, I., Morávek, J., B -valuations of graphs, Czech. Math. J. 22 (1972), 338-351. (1972) Zbl0247.05148MR0294159
  11. 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
  12. Nebeský, L., On cubes and dichotomic trees, Čas. Pěst. Mat. 99 (1974), 164-167. (1974) Zbl0277.05101MR0354425
  13. Nekri, M., Berrachedi, A., 10.1051/ro:2004027, RAIRO, Oper. Res. 38 (2004), 295-303. (2004) Zbl1114.05023MR2178082DOI10.1051/ro:2004027
  14. Wagner, A., Corneil, D. G., 10.1137/0219038, SIAM J. Comput. 19 (1990), 570-590. (1990) Zbl0698.68054MR1041546DOI10.1137/0219038

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.