2016/09/20 by Cioabă, Sebastian M., Elzinga, Randall J., Markiewitz, Michelle +2
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1609.05995
Graham and Pollak showed that the vertices of any connected graph G can be assigned t-tuples with entries in \0, a, b\, called addresses, such that the distance in G between any two vertices equals the number of positions in their addresses where one of the addresses equals a and the other equals b. In this paper, we are interested in determining the minimum value of such t for various families of graphs. We develop two ways to obtain this value for the Hamming graphs and present a lower bound for the triangular graphs.