Metric dimension of imprimitive distance-regular graphs

Robert Bailey
Grenfell Campus, Memorial University

PDF

Minisymposium: METRIC DIMENSION AND RELATED PARAMETERS

Content: The metric dimension of a graph $\Gamma$ is the least size of a set of vertices $\{v_1, \ldots, v_m\}$ with the property that, for any vertex $w$, the list of distances from $w$ to each of $v_1, \ldots, v_m$ uniquely identifies $w$. In this talk, we consider the metric dimension of imprimitive distance-regular graphs, which are either bipartite or antipodal (i.e. being at distance $0$ or $d$ is an equivalence relation on the vertices, where $d$ is the diameter). We use a theorem of Alfuraidan and Hall, along with the operations of ``halving'' and ``folding'', to reduce the problem to primitive graphs, where known results of Babai apply, except when the diameter is between $3$ and $6$. In this case, especially when the diameter is $3$, we see that unexpected things start to happen.

Back to all abstracts