Combinatorial identification problems and graph powers
Problèmes d'identification combinatoire et puissances de graphes
Résumé
The thesis deals in a first with algorithmic and combinatorial properties of different variations on identifying codes in undirected graphs, a theoretical model for problems of detection and localization in networks. These issues led us to consider a notion of powers of graphs, which we then investigate into several directions.
Les codes identifiants dans les graphes modélisent des systèmes de détection et de localisation à distance de pannes multiples dans les réseaux. Nous abordons dans une première partie différents problèmes de nature algorithmique ou structurelle concernant plusieurs variations autour de ces codes ; en particulier, nous obtenons de nombreux résultats quant à la structure des graphes sans jumeaux. Ces questions nous amènent dans une deuxième partie à considérer une notion de puissance de graphe, que nous étudions plus avant. Nous obtenons en particulier des résultats de type extrémal et nous consacrons l'étude des racines carrées de graphes.