Title

On The Dimension Of Trees

Keywords

Infinity norm; Isometric embeddings; Trees

Abstract

We consider isometric embedding of trees into the infinite graph Zm whose vertices are the m-dimensional lattice points where two vertices a=(a1,a2,...,am) and b=(b1,b2,...,bm) are adjacent if and only if |ai-bi|≤1 for 1≤i≤m. Linial, London, and Rabinovich have shown that this can be done with m≤1.7095log2t, where t is the number of leaves. In this note, we sketch a proof that ⌈log2t⌉≤m≤⌈1.45log2t⌉. © 2005 Elsevier B.V. All rights reserved.

Publication Date

5-6-2005

Publication Title

Discrete Mathematics

Volume

294

Issue

3

Number of Pages

279-283

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.disc.2004.11.013

Socpus ID

17644421456 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/17644421456

This document is currently not available here.

Share

COinS