On Iiro Honkala’s Contributions to Identifying Codes

Issue title: Codes, Graphs, Coverings, and Identification: Special Issue Honoring the 60-th Birthday of Professor Iiro Honkala

Guest editors: Vesa Halava, Jarkko Kari and Tero Laihonen

Article type: Research Article

Authors: Hudry, Olivier^{a; *} | Ville, Junnila^b | Lobstein, Antoine^c

Affiliations: [a] Télécom Paris, France. olivier.hudry@telecom-paris.fr | [b] University of Turku, Finland. viljun@utu.fi | [c] CNRS, Université Paris-Saclay, France. lobstein@lri.fr

Correspondence: [*] Address for correspondence: Département Informatique et Réseaux de Télécom Paris, France.

Abstract: A set C of vertices in a graph G = (V, E) is an identifying code if it is dominating and any two vertices of V are dominated by distinct sets of codewords. This paper presents a survey of Iiro Honkala’s contributions to the study of identifying codes with respect to several aspects: complexity of computing an identifying code, combinatorics in binary Hamming spaces, infinite grids, relationships between identifying codes and usual parameters in graphs, structural properties of graphs admitting identifying codes, and number of optimal identifying codes.

Keywords: graph theory, combinatorics, identifying codes, domination, separation, twin-free graphs, complexity, binary Hamming spaces, infinite grids, classic parameters of graphs, number of optimal solutions

DOI: 10.3233/FI-242178

Journal: Fundamenta Informaticae, vol. 191, no. 3-4, pp. 165-196, 2024