  Graham and Pollak showed that the vertices of any graph $G$ can be addressed
with $N$-tuples of three symbols, such that the distance between any two
vertices may be easily determined from their addresses. An addressing is
optimal if its length $N$ is minimum possible.
  In this paper, we determine an addressing of length $k(n-k)$ for the Johnson
graphs $J(n,k)$ and we show that our addressing is optimal when $k=1$ or when
$k=2, n=4,5,6$, but not when $n=6$ and $k=3$. We study the addressing problem
as well as a variation of it in which the alphabet used has more than three
symbols, for other graphs such as complete multipartite graphs and odd cycles.
We also present computations describing the distribution of the minimum length
of addressings for connected graphs with up to $10$ vertices. Motivated by
these computations we settle a problem of Graham, showing that most graphs on
$n$ vertices have an addressing of length at most $n-(2-o(1))\log_2 n$.
