In this thesis, we study the complexity of the problem of exploration by a mobile agent in dynamic graphs. A mobile entity (called agent) moving in a dynamic graph has to traverse/visit each of its vertices at least once. This fundamental problem in computating by mobile agents has been well-studied in static graphs since the original paper of Claude Shannon. However, for highly dynamic graphs, only the case of periodic dynamic graphs has been studied. We study this problem in two families of dynamic graphs, periodically-varying graphs (PV-graphs) and T-interval-connected dynamic graphs. The obtained results improve the existing results and give optimal bounds on the studied problems. A PV-graph is defined by a set of carriers infinitely following their prescribed route along the network stations. In 2013, Flocchini, Mans and Santoro studied the problem in the case when the agent must always travel on the carriers and thus cannot wait at a station. Our work investigates the ability of an agent that can wait at the stations. We exhibit necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the worst-case optimal number of moves by a multiplicative factor of at least $\Theta(p)$, while the time complexity is reduced to $\Theta(n\cdot p)$, where $n$, $k$, and $p$ denote respectively the number of sites, the number of carriers, and the maximal period. (In any connected PV-graph, we have $n \leq k\cdot p$.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected PV-graphs). Finally this ability allows the agent to produce a complete map of the PV-graph, in addition to just explore it. In the second part of the thesis, we considered the same problem (exploration) in T-interval-connected dynamic graphs. A dynamic graph is T-interval-connected ($T \geq 1$) if for every consecutive $T$ rounds, there exists a stable connected spanning subgraph. We considered T-interval-connected dynamic graphs such that the underlying graph is a ring of size $n$. We show that in the worst case the complexity is $2n-T-2$ time units if the agent knows the dynamic of the graph, and $\frac{n-1}{T} \delta +n \pm \Theta(\delta) -1$ time units if the agent does not know the dynamics of the graph, where $\delta$ is the maximum time between two successive appearances of an edge. Furthermore, we generalize these results by considering another family of underlying graphs, cactus graphs. A cactus graph is a connected graph in which any two simple cycles have at most one vertex in common. We propose an algorithm that allows the agent to explore these dynamic graphs in at most $2^{O(\sqrt{log n})} n$ time units. We show that the lower bound of our algorithm is $2^{\Omega(\sqrt{log n})} n$ time units.
