On the metric dimension of imprimitive distance-regular graphs (Q505687)

A resolving set for a graph is a set of vertices \(S\) so that a vertex of the graph is uniquely determined by the list of the distances from it to the elements of \(S\). That is, for distinct vertices \(x\) and \(y\), there is at least one \(s \in S\) so that \(d(x,s) \neq d(y,s)\). The metric dimension of a graph \(G\), denoted \(\mu(G)\), is the size of the smallest possible resolving set for \(G\). A distance-regular graph is primitive if all of its distance-\(i\) graphs (for \(i\) less than or equal to the diameter \(d\)) are connected. For primitive graphs, upper bounds on the metric dimension due to Babai are known. This paper investigates the metric dimensions of imprimitive distance regular graphs, obtaining upper bounds on the metric dimensions of a number of classes of graphs by applying Babai's bounds to closely related primitive graphs. Specifically, the paper makes heavy use of the notions of the halved graph and the folded graph of a graph \(G\). If \(G\) is a bipartite distance-regular graph, then its distance-2 graph has two connected components, called the halved graphs of \(G\). If a distance-regular graph is not bipartite, it is \(t\)-antipodal, meaning that the distance-\(d\) graph is a disjoint union of cliques of size \(t\). (The constant size of these cliques is a consequence of distance-regularity.) The folded graph is the graph on the set of these cliques, with two cliques adjacent in the folded graph exactly when they contain vertices which are adjacent in \(G\). The main importance of these notions is that an imprimitive distance-regular graph with valency \(k \geq 3\) can be reduced to a primitive one by halving the graph at most once and folding the graph at most once. Thus, the following theorems proven in the paper allow the authors to extend Babai's bounds to a number of classes of imprimitive distance regular graphs. Theorem 2.1: If \(\Gamma\) is a connected bipartite graph with halved graphs \(\Gamma^{+}\) and \(\Gamma^{-}\), then \(\mu(\Gamma) \leq \mu(\Gamma^{+}) + \mu(\Gamma^{-})\). Theorem 2.2: If \(\Gamma\) is an \((r+1)\)-antipodal graph with folded graph \(\overline{\Gamma}\), then \(\mu(\Gamma)\) is bounded above by \(r(\mu(\overline{\Gamma})+1)\). (This bound can be improved to \(r(\mu(\overline{\Gamma}))\) under certain conditions on \(\Gamma\).) The authors also use other methods to find tighter bounds on two classes of graphs. The first are the Taylor graphs, which are antipodal 2-covers of \(K_{n+1}\). Taylor graphs are in one-to-one-correspondence with regular two-graphs, defined as follows. A two-graph \(D\) is a pair \((V,\beta)\), where \(V\) is a set, and \(\beta\) is a collection of 3-subsets of \(V\) with the property that any 4-subset of \(V\) contains an even number of members of \(\beta\). From \(x \in V\), we can form a new graph, called a \textit{descendant} of \(D\), with vertex set \(V \setminus \{x\}\) and edges exactly those pairs \(\{y,z\}\) such that \(\{x,y,z\} \in \beta\). The paper proves a theorem relating the metric dimension of a Taylor graph to the metric dimensions of the descendants of a corresponding two-graph, and combines this with Babai's bounds to bound the metric dimension of a Taylor graph. The authors end by considering graphs realized as the incidence graph of a symmetric design with a null polarity. A design having a null polarity is equivalent to the existence of an ordering of the points and blocks of the design so that the incidence matrix is symmetric with zeroes on the main diagonal -- i.e. it is the adjacency matrix of a simple graph. Again, the authors show a relationship between the metric dimension of the incidence graph of the design (the graph whose vertices are the union of the points and blocks, with edges showing incidences), and the metric dimension of the graph described by the incidence matrix, allowing the authors to bound the metric dimension of the incidence graph.