Resolving sets in Affine planes

Daniele Bartoli
Department of Mathematics, Ghent University

Tam\'as H\'eger
MTA-ELTE GAC Research Group, E\"{o}tv\"{o}s Lor\'and University

Gy\"{o}rgy Kiss
Department of Geometry and MTA-ELTE GAC Reasearch Group, E\"{o}tv\"{o}s Lor\'and University

Marcella Tak\'ats
Department of Computer Science, E\"{o}tv\"{o}s Lor\'and University

PDF

Minisymposium: FINITE GEOMETRY

Content: Let $\Gamma=(V,E)$ be a graph. A vertex $v\in V$ is resolved by a vertex-set $S = \{v_1, \ldots, v_n\}$ if its (ordered) distance list $(d(v, v_1), \ldots, d(v, v_n))$ with respect to $S$ is unique. S is a resolving set in $\Gamma$ if every vertex $v\in V$ is resolved by $S$. The metric dimension of $\Gamma$ is the size of the smallest resolving set in it. In a recent work H\'eger and Tak\'ats (\emph{Resolving sets and semi-resolving sets in finite projective planes}, Electron. J. Combin. {\bf 19} \#P30, 2012) showed that the metric dimension of the incidence graph of a finite projective plane of order $q \geq 23$ is $4q -4$ and they classified all the resolving sets of that size. We analyze the problem in the affine case and we prove that the metric dimension of $AG(2,q)$ is at most $3q-4$. The main differences in the approach rely on the non-applicability of the duality principle, due to the presence of parallel lines.

Back to all abstracts