Home
Scholarly Works
Addressing graph products and distance-regular...
Journal article

Addressing graph products and distance-regular graphs

Abstract

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.

Authors

Cioabă SM; Elzinga RJ; Markiewitz M; Vander Meulen K; Vanderwoerd T

Journal

Discrete Applied Mathematics, Vol. 229, , pp. 46–54

Publisher

Elsevier

Publication Date

October 1, 2017

DOI

10.1016/j.dam.2017.05.018

ISSN

0166-218X

Contact the Experts team