A Binary Analogous of the Addressing Problem for Weighted Graphs

In [1], Graham and Pollak introduced the addressing problem. Addressing number of a graph is defined as the shortest length strings (addresses) over the alphabet ${0,1,*}$ to the vertices such that the distance between each pair of the addresses of two nodes is equal to the graph distance of them. When the alphabet is binary, there are graphs for which no such stings exist. In this work, we introduce a variant of addressing problem for weighted graphs over the alphabet $0,1$. This problem generalizes the well-known minimum length error correction code problem. We find upper and lower bounds for this parameter. For small size graphs, we find the exact value of this parameter. Finally, we define and study the normalized version of this parameter.