The work presented in this document deals with identifying codes in graphs. This notion, introduced in the late 1990's, models fault-detection problems in networks. An identifying code can be seen as a variant of the domination problem, with an additional constraint for identifying the vertices. Finding the minimum cardinality of such a code is an NP-difficult problem. The results presented herein deal with four topics. The first topic is related to regular structures (grids, cycles, hypercubes, products of cliques, Sierpiński graphs), for which some results on the minimum cardinality of a code (bounds and exact values) are presented. Then, algorithmic aspects are developed, one the one hand about polynomial algorithms designed for specific graph classes (trees, fasciagraphs), on the other hand about the approximability of the problem. Some structural questions are then addressed, namely the construction of extremal graphs, the construction of families of graphs admitting a code of small cardinality, and the structure (degrees, induced subgraphs, etc.) of graphs admitting such a code. Finally, a new variant of the problem is presented, that is adaptive identifying codes. This variant enables one to model a situation where we may take advantage of the dynamic aspect of the problem, and hope to query significantly less vertices than in the static case. In particular, we explicit in this document several links that relate identifying codes to other kind of structures, such as dominating sets, superimposed codes, projective planes, or Rényi search games.
