The lattice dimension of a tree

2004/02/15 by Sergeĭ Ovchinnikov, Sergei Ovchinnikov, Ovchinnikov, Sergei
Computer Science · Mathematics · #05C05 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO #msc:05C05

paper · pdf · doi:10.48550/arxiv.math/0402246

3 pages

arxiv created 2004/02/15 · openalex publication_date 2004/02/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The lattice dimension of a graph G is the minimal dimension of a cubic lattice in which G can be isometrically embedded. We prove that the lattice dimension of a tree with n leaves is \lceil n/2 \rceil.

Related

• The lattice dimension of a graph
• On the Boolean dimension of a graph and other related parameters
• Product Dimension of Forests and Bounded Treewidth Graphs
• Tree Dimension and the Sauer-Shelah Dichotomy
• Graphs that are minor minimal with respect to dimension