On the metric dimension of incidence graphs

A resolving set for a graph Gamma is a collection of vertices S, chosen so that for each vertex nu, the list of distances from nu to the members of S uniquely specifies nu. The metric dimension mu(Gamma) is the smallest size of a resolving set for Gamma. We consider the metric dimension of two families of incidence graphs: incidence graphs of symmetric designs, and incidence graphs of symmetric transversal designs (i.e. symmetric nets). These graphs are the bipartite distance-regular graphs of diameter 3, and the bipartite, antipodal distance-regular graphs of diameter 4, respectively. In each case, we use the probabilistic method in the manner used by Babai to obtain bounds on the metric dimension of strongly regular graphs, and are able to show that mu(Gamma) = 0(root n log n) (where n is the number of vertices). (C) 2018 Elsevier B.V. All rights reserved.