Resolving sets and semi-resolving sets in finite projective planes
| Autor: | Tamás Héger, Marcella Takáts |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
Applied Mathematics
010102 general mathematics 05C12 05B25 0102 computer and information sciences 01 natural sciences Graph Theoretical Computer Science Metric dimension Vertex (geometry) Combinatorics Computational Theory and Mathematics Blocking set 010201 computation theory & mathematics FOS: Mathematics Bipartite graph Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) Geometry and Topology Projective plane 0101 mathematics Resolving set Mathematics |
| Zdroj: | Scopus-Elsevier |
| Popis: | We show that the metric dimension 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 $\mathrm{PG}(2,q)$, the Desarguesian projective plane of order $q$. We prove that for a semi-resolving set $S$ in the incidence graph of $\mathrm{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 $\mathrm{PG}(2,q)$ has size $2q+2\sqrt{q}$. Comment: 21 pages, 3 figures. Version 3 contains clarifications and minor corrections regarding the list and the figure of the 32 types of smallest resolving sets, and a supplementary page explaining these modifications |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|