Problèmes d'identification combinatoire et puissances de graphes
Institution:
Paris, Télécom ParisTechDisciplines:
Directors:
Abstract EN:
Identifying codes in graphs provide a theoretical model for systems that can identify within a given distance sets of faulty nodes in a network. The thesis deals in a first part with algorithmic and combinatorial properties of different variations on identifying codes in non-oriented graphs, including in particular numerous results about the structure of twin-free graphs. These issues led us to consider a notion of powers of graphs, which we investigate into several directions in a second part. We study in particular extremal results and the notion of square-root of a graph.
Abstract FR:
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.