On the metric dimension of imprimitive distance-regular graphs

Robert F. Bailey

Published 2013-12-17, updated 2014-09-17Version 3

A resolving set for a graph $\Gamma$ is a collection of vertices $S$, chosen so that for each vertex $v$, the list of distances from $v$ to the members of $S$ uniquely specifies $v$. The metric dimension of $\Gamma$ is the smallest size of a resolving set for $\Gamma$. Much attention has been paid to the metric dimension of distance-regular graphs. Work of Babai from the early 1980s yields general bounds on the metric dimension of primitive distance-regular graphs in terms of their parameters. In this paper, by considering three families of imprimitive distance-regular graphs (bipartite doubles, Taylor graphs, and the incidence graphs of symmetric designs), we show that this holds for some infinite families of imprimitive graphs, and fails for some others.