We reflect on an addressing scheme for simple graphs G
introduced by Graham and Pollak. This scheme is equivalent to 
partitioning the distance multigraph D(G) into
complete bipartite graphs. We then introduce
an addressing scheme based on partitioning
the distance multigraph D(G) into cliques.
We consequently seek the minimum number of
cliques needed to partition the edge set of D(G).
We use a fractional analogue of this parameter to find
lower bounds for the distance graphs of various classes of graphs.
Some of the bounds are shown to be exact.