Eternal feedback vertex sets: A new graph protection model using guards

Autor:	Nour Dyab, Mohammed Lalou, Hamamache Kheddouci
Rok vydání:	2023
Předmět:	Discrete Mathematics and Combinatorics
Zdroj:	Discrete Mathematics, Algorithms and Applications.
ISSN:	1793-8317 1793-8309
Popis:	Graph protection using mobile guards has received a lot of attention in the literature. It has been considered in different forms, including Eternal Dominating set, Eternal Independent set and Eternal Vertex Cover set. In this paper, we introduce and study two new models of graph protection, namely Eternal Feedback Vertex Sets (EFVS) and m-Eternal Feedback Vertex Sets (m-EFVS). 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. We prove bounds for both the eternal and m-eternal feedback vertex numbers on, mainly, distance graphs, circulant graphs and grids. Also, we deduce other inequalities for both parameters on cycles, complete graphs and complete bipartite graphs.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::b5cb5c91278fab3897ebdb578f4738aa https://doi.org/10.1142/s1793830923500301 Zobrazit plný text záznamu