The metric dimension of small distance-regular and strongly regular graphs

Robert F. Bailey

Published 2013-12-17Version 1

A {\em 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 {\em metric dimension} of $\Gamma$ is the smallest size of a resolving set for $\Gamma$. A graph is {\em distance-regular} if, for any two vertices $u,v$ at each distance $i$, the number of neighbours of $v$ at each possible distance from $u$ (i.e. $i-1$, $i$ or $i+1$) depends only on the distance $i$, and not on the choice of vertices $u,v$. The class of distance-regular graphs includes all distance-transitive graphs and all strongly regular graphs. In this paper, we present the results of computer calculations which have found the metric dimension of all distance-regular graphs on up to 34 vertices, low-valency distance transitive graphs on up to 100 vertices, strongly regular graphs on up to 45 vertices, rank-$3$ strongly regular graphs on under 100 vertices, as well as certain other distance-regular graphs.