Resolving sets in Johnson and Kneser graphs
Presented by Mr. Antonio GONZáLEZ
Type: Oral presentation
Track: General session
A set of vertices $S$ resolves a graph $G$ if every vertex is uniquely determined by its vector of distances to the vertices in $S$. The metric dimension of $G$ is the minimum cardinality of a resolving set of $G$. In this work, we provide different approaches to the problem of determining resolving sets of Johnson and Kneser graphs, which give rise to significant bounds for the metric dimension. Concretely, we deal with combinatorial structures such as finite geometries, symmetric designs and toroidal grids which arise as new useful tools to be applied in resolvability in graphs. The talk shall be mainly focussed on finite geometries.