### Thesis of Nour Dyab

**Subject:**

**Defense date:**24/10/2023

**Advisor:**Hamamache Kheddouci

**Summary:**

This thesis aims to develop a model for graph protection using mobile guards, specifically focusing on the concept of eternal feedback vertex sets. The problem of protecting a graph using mobile guards has been extensively studied in the literature. This problem involves defending the vertices, as well as edges, of a graph G against any attack using defence units, called guards, stationed at the vertices of G. Our primary interest lies in protecting graphs against infinite sequences of attacks, where each attack is executed one at a time. A protection problem can be modelled by a two-player game between a defender and an attacker. In this game, the defender selects the initial configuration of guards in the first turn and must defend all vertices of G against any attack by reconfiguring the guards at each subsequent turn. On the other hand, the attacker chooses the location of each attack at each turn. An attack is considered defended if a guard can be moved to the attacked vertex via an edge. The defender wins the game if they successfully defend the graph against every sequence of attacks, while the attacker wins if he manages to breach the defence. Importantly, the sequence of attacks can be of infinite length. In this thesis, we introduce two new variants of the graph protection problem, namely Eternal Feedback Vertex Sets (EFVS) and m-Eternal Feedback Vertex Sets (m-EFVS). The two variants are modelled in the same way using a two-player game, with the specific condition that the set of vertices chosen by the defender to receive guards must simultaneously form a feedback vertex set and a dominating set in each turn. In other words, the Eternal Feedback Vertex Set on a graph can be seen as an infinite game between a defender and an attacker, where the defender chooses a set of guards F_{i }at each turn i, i ≥ 1. At turn i, the attacker chooses a vertex r_{i}, called an attack, in V \Fi-1 and the defender must defend the attack by moving to r_{i} a guard from a vertex v_{j }adjacent to r_{i}. The new guards configuration is F_{i} = F_{i−1} ∪ {r_{i}} \ {v_{j}}. The sets F_{i}, for any i ≥ 1, must be dominating and feedback vertex sets. In the case where the defender protects vertices by moving more than one guard, we talk about the m-Eternal Feedback Vertex Sets. Our primary focus in this study is to propose a new protective model that utilizes mobile guards to protect the vertices of a graph. We provide formal definitions of our new models of graph protection, namely the Eternal Feedback vertex set and Eternal Feedback vertex set. Both models are based on an initial selection of a feedback vertex set (FVS), where a vertex in FVS can be replaced with a neighboring vertex such that the resulting set is a FVS too. Then, we compare the two parameters; the eternal and m-eternal numbers, F^{∞} and F^{∞}_{m}, corresponding to the smallest eternal (m- eternal) feedback set of the graph, with known graph parameters. Consequently, we deduce some inequalities for F^{∞} and F^{∞}_{m} on cycles, complete graphs and complete bipartite graphs. Also, we provide a detailed study of both variants on grids, distance and circulant graphs. Also, we consider the class of interval graphs, we prove that the eternal feedback vertex number F^{∞}(G) on an interval graph G depends on the F^{∞} of cliques in G. And we develop a linear algorithm for finding the eternal feedback vertex set on G, which utilizes a graph partitioning method as a prepossessing step, and then selects the guards from each partition independently. Finally, we explore strategies for constructing an EFVS and determining the eternal feedback vertex number on various classes of graphs, including k-dimensional graphs, wheel graphs, and fan graphs. We also develop a linear algorithm for finding the eternal feedback vertex set in k-spiral graphs. Finally, we conclude the thesis by providing a comprehensive summary of the presented work and highlighting intriguing open problems for further investigation.

**Jury:**

Pr. Olivier Togni | Professeur(e) | Université de Bourgogne | Rapporteur(e) |

Pr. Abdallah Makhoul | Professeur(e) | Université de Franche-Comté | Rapporteur(e) |

Pr. Salima Benbernou | Professeur(e) | Université Paris Cité | Examinateur(trice) |

Dr. Maidoun Mortada | Maître de conférence | Université libanaise | Examinateur(trice) |

Dr. Nora Faci | Maître de conférence | Université Lyon 1 | Examinateur(trice) |

Dr. Mohamed Lalou | Maître de conférence | Université de Bourgogne | Examinateur(trice) |

Pr. Hamamache Kheddouci | Professeur(e) | Université Lyon 1 | Directeur(trice) de thèse |