Geodesic
A note on the cubical dimension of new classes of binary trees
Czechoslovak Mathematical Journal, Tome 65 (2015) no. 1, pp. 151-160

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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},
     publisher = {mathdoc},
     volume = {65},
     number = {1},
     year = {2015},
     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
PB  - mathdoc
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
%I mathdoc
%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

Cité par Sources :