Dimension of a Caterpillar

Abstract

A $k$-labeling of a graph is a labeling of the vertices of the graph by $k$-tuples of non-negative integers such that two vertices of $G$ are adjacent if and only if their label $k$-tuples differ in each coordinate. The dimension of a graph $G$ is the least $k$ such that $G$ has a $k$-labeling.

Lovász et al. showed that for $n\ge 3$, the dimension of a path of length $n$ is $({\log }_{2}n{)}^{+}$. Lovász et al. and Evans et al. determined the dimension of a cycle of length $n$ for most values of $n$. In the present paper, we obtain the dimension of a caterpillar or provide close bounds for it in various cases.