Department of Mathematics

Indian Institute Of Technology Madras , Chennai

Identification problems in graphs.

Speaker : Florent Foucaud


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.

Key Speaker Florent Foucaud
Place NAC 522
Start Time 3:00 PM
Finish Time 4:00 PM
External Link None