Abstract :

We will introduce the audience to the topic of certain types of identification problems in graphs such as identifying codes, locating-dominating sets and the metric dimension. In these types of problems, we wish to choose a subset of elements that "covers" the graph in such a way that all elements are "identified" (i.e. uniquely determined) by our choice. Several definitions will be considered, and a selection of recent advances will be presented. One of the oldest results in the area is Bondy's celebrated theorem on set systems [J. A. Bondy. Induced subsets. Journal of Combinatorial Theory, Series B 12:201-202, 1972]. We will start by presenting it. Some algorithmic aspects will also be addressed.