# Resolving Sets and Semi-Resolving Sets in Finite Projective Planes

### Abstract

In a graph $\Gamma=(V,E)$ a vertex $v$ is *resolved* by a vertex-set $S=\{v_1,\ldots,v_n\}$ if its (ordered) distance list with respect to $S$, $(d(v,v_1),\ldots,d(v,v_n))$, is unique. A set $A\subset V$ is resolved by $S$ if all its elements are resolved by $S$. $S$ is a *resolving set* in $\Gamma$ if it resolves $V$. The *metric dimension of *$\Gamma$ is the size of the smallest resolving set in it. In a bipartite graph a *semi-resolving set* is a set of vertices in one of the vertex classes that resolves the other class.

We show that the metric dimension of the incidence graph of a finite projective plane of order $q\geq 23$ is $4q-4$, and describe all resolving sets of that size. Let $\tau_2$ denote the size of the smallest double blocking set in PG$(2,q)$, the Desarguesian projective plane of order $q$. We prove that for a semi-resolving set $S$ in the incidence graph of PG$(2,q)$, $|S|\geq \min \{2q+q/4-3, \tau_2-2\}$ holds. In particular, if $q\geq9$ is a square, then the smallest semi-resolving set in PG$(2,q)$ has size $2q+2\sqrt{q}$. As a corollary, we get that a blocking semioval in PG$(2, q)$, $q\geq 4$, has at least $9q/4-3$ points.

A corrigendum was added to this paper on March 3, 2017.