On the dimension of trees (Q5916234)
From MaRDI portal
scientific article; zbMATH DE number 2174861
Language | Label | Description | Also known as |
---|---|---|---|
English | On the dimension of trees |
scientific article; zbMATH DE number 2174861 |
Statements
On the dimension of trees (English)
0 references
10 June 2005
0 references
This short article considers the problem of isometrically embedding a tree into the graph \(Z_m\), which has as vertices the lattice points of the \(m\)-dimensional space. Two vertices \(a\), \(b\) are adjacent if and only if \(| a_i-b_i| \leq 1\), where \(a_i\), \(b_i\) are the vertex coordinates. The authors show that the embedding is possible if \(\lceil\log_2 t\rceil\leq m \leq \lceil1.45\log_2 t\rceil\), thus improving the lower bound and the previously best known upper bound of about \(1.71\log_2 t\) (\(t\) is the number of leaves of the tree).
0 references
isometric embedding
0 references
infinity norm
0 references
trees
0 references