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

Title:

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

Creator:

Kabyl, Kamal, Berrachedi, Abdelhafid, and Sopena, Éric

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:f32dd603-9f34-4ec5-8a1a-0a45aef4e311
uuid:f32dd603-9f34-4ec5-8a1a-0a45aef4e311

Subject:

cubical dimension, embedding, Havel's conjecture, hypercube, and tree

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

151-160

Source:

Czechoslovak Mathematical Journal | 2015 Volume:65 | Number:1

Harvested from:

CDK

Metadata only:

false