Self-stabilization, introduced by Dijkstra computer in 1973, is a technique that allows the design of fault-tolerant distributed systems. A distributed self-stabilizing system can automatically retrieve its correct behavior after a failure of one or more elements in the system. Moreover, this has to be achieved in finite time and without any external intervention, making self-stabilization a very interesting technique for the design of robust distributed systems.

Researchers have extensively studied structural properties of graphs. Several results (analytical and algorithmic) have been proposed for constructing, detecting and bringing structural properties in graphs. Unfortunately, these results were only developed in their sequential and centralized forms thus limiting their use in distributed, dynamic or mobile systems.

This thesis aims to overcome these limitations by focusing on distributed and dynamic structural study of graphs. The main objective is to study graph decompositions and search for specific patterns in graphs using self-stabilizing and distributed algorithms. Porting these theoretical results on autonomous distributed systems with such algorithms become then useful for designing efficient protocols and applications.