Resolving sets and semi-resolving sets in finite projective planes (Q1953337)

Summary: In a graph \(\Gamma=(V,E)\) a vertex \(v\) is resolved by a vertex-set \(S=\{v_1,\dots,v_n\}\) if its (ordered) distance list with respect to \(S\), (\(d(v,v_1),\dots,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.