On the metric dimension of incidence graphs.

A resolving set for a graph Γ 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 μ ( Γ ) is the smallest size of a resolving set for Γ . 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 μ ( Γ ) = O ( n log n ) (where n is the number of vertices). [ABSTRACT FROM AUTHOR]