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

K Kabyl, A Berrachedi, É Sopena - Czechoslovak Mathematical Journal, 2015 - Springer
K Kabyl, A Berrachedi, É Sopena
Czechoslovak Mathematical Journal, 2015Springer
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 …
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 ⩾ 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.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果