Geodesic
A note on the cubical dimension of new classes of binary trees
Czechoslovak Mathematical Journal, Tome 65 (2015) no. 1, pp. 151-160
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-015-0165-6
Classification : 05C05, 05C60
Keywords: cubical dimension; embedding; Havel's conjecture; hypercube; tree 
@article{10_1007_s10587_015_0165_6,
     author = {Kabyl, Kamal and Berrachedi, Abdelhafid and Sopena, \'Eric},
     title = {A note on the cubical dimension of new classes of binary trees},
     journal = {Czechoslovak Mathematical Journal},
     pages = {151--160},
     year = {2015},
     volume = {65},
     number = {1},
     doi = {10.1007/s10587-015-0165-6},
     mrnumber = {3336030},
     zbl = {06433726},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0165-6/}
}
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
SP  - 151
EP  - 160
VL  - 65
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0165-6/
DO  - 10.1007/s10587-015-0165-6
LA  - en
ID  - 10_1007_s10587_015_0165_6
ER  - 
%0 Journal Article
%A Kabyl, Kamal
%A Berrachedi, Abdelhafid
%A Sopena, Éric
%T A note on the cubical dimension of new classes of binary trees
%J Czechoslovak Mathematical Journal
%D 2015
%P 151-160
%V 65
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0165-6/
%R 10.1007/s10587-015-0165-6
%G en
%F 10_1007_s10587_015_0165_6
Kabyl, Kamal; Berrachedi, Abdelhafid; Sopena, Éric. A note on the cubical dimension of new classes of binary trees. Czechoslovak Mathematical Journal, Tome 65 (2015) no. 1, pp. 151-160. doi: 10.1007/s10587-015-0165-6

[1] Bezrukov, S., Monien, B., Unger, W., Wechsung, G.: Embedding ladders and caterpillars into the hypercube. Discrete Appl. Math. 83 (1998), 21-29. | DOI | MR | Zbl

[2] Chen, C.-C., Chen, R.-J.: Compact embedding of binary trees into hypercubes. Inf. Process. Lett. 54 (1995), 69-72. | DOI | MR | Zbl

[3] Choudum, S. A., Lavanya, S.: Embedding a subclass of trees into hypercubes. Discrete Math. 311 (2011), 866-871. | DOI | MR | Zbl

[4] Choudum, S. A., Raman, I.: Embedding height balanced trees and Fibonacci trees in hypercubes. J. Appl. Math. Comput. 30 (2009), 39-52. | DOI | MR | Zbl

[5] Dvořák, T.: Dense sets and embedding binary trees into hypercubes. Discrete Appl. Math. 155 (2007), 506-514. | DOI | MR | Zbl

[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 | MR

[7] Harary, F., Lewinter, M., Widulski, W.: On two-legged caterpillars which span hypercubes. Congr. Numer. 66 (1988), 103-108. | MR | Zbl

[8] Havel, I.: On Hamiltonian circuits and spanning trees of hypercubes. Čas. Pěst. Mat. 109 (1984), 135-152. | MR | Zbl

[9] Havel, I., Liebl, P.: Embedding the dichotomic tree into the $n$-cube. Čas. Pěst. Mat. 97 Czech (1972), 201-205. | MR | Zbl

[10] Havel, I., Morávek, J.: {$B$}-valuations of graphs. Czech. Math. J. 22 (1972), 338-351. | MR | Zbl

[11] Kobeissi, M., Mollard, M.: Spanning graphs of hypercubes: starlike and double starlike trees. Discrete Math. 244 (2002), 231-239. | DOI | MR | Zbl

[12] Nebeský, L.: On cubes and dichotomic trees. Čas. Pěst. Mat. 99 (1974), 164-167. | MR | Zbl

[13] Nekri, M., Berrachedi, A.: Two new classes of trees embeddable into hypercubes. RAIRO, Oper. Res. 38 (2004), 295-303. | DOI | MR | Zbl

[14] Wagner, A., Corneil, D. G.: Embedding trees in a hypercube is NP-complete. SIAM J. Comput. 19 (1990), 570-590. | DOI | MR | Zbl

Cité par Sources :