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

Czechoslovak Mathematical Journal

Abdelhafid Berrachedi¹  Kamal Kabyl²  Éric Sopena³ 

[1] Faculty of Mathematics, U.S.T.H.B, B.P. 32 El Alia, Bab-Ezzouar 16111, Algiers, Algeria;Laboratory of Modeling and Optimization of Systems, University of Bejaia, 06000 Bejaia, Algeria and Faculty of Mathematics, U.S.T.H.B, B.P. 32 El Alia, Bab-Ezzouar 16111, Algiers, Algeria;Univ. Bordeaux, LaBRI, UMR5800, F-33400 Talence, France, and CNRS, LaBRI, UMR5800, F-33400 Talence, France

关键词: cubical dimension;    embedding;    Havel's conjecture;    hypercube;    tree;   

DOI  :  

学科分类：数学（综合）

来源: Akademie Ved Ceske Republiky

【 摘 要 】

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\geq1$, 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.

【 授权许可】

Unknown