A new lower bound for the eternal vertex cover number of graphs
J Babu, V Prabhakaran - Journal of Combinatorial Optimization, 2022 - Springer
The main result in this paper is a new lower bound to the eternal vertex cover number (evc
number) of an arbitrary graph G in terms of the size of the smallest vertex cover in G that …
number) of an arbitrary graph G in terms of the size of the smallest vertex cover in G that …
A substructure based lower bound for eternal vertex cover number
J Babu, V Prabhakaran, A Sharma - Theoretical Computer Science, 2021 - Elsevier
The eternal vertex cover (EVC) problem is to compute the minimum number of guards to be
placed on the vertices of a graph so that any sequence of attacks on its edges can be …
placed on the vertices of a graph so that any sequence of attacks on its edges can be …
On graphs whose eternal vertex cover number and vertex cover number coincide
The eternal vertex cover problem is a variant of the classical vertex cover problem defined in
terms of an infinite attacker–defender game played on a graph. In each round of the game …
terms of an infinite attacker–defender game played on a graph. In each round of the game …
Eternal connected vertex cover problem
T Fujito, T Nakamura - Theory and Applications of Models of Computation …, 2020 - Springer
A new variant of the classic problem of Vertex Cover (VC) is introduced. Either Connected
Vertex Cover (CVC) or Eternal Vertex Cover (EVC) is already a variant of VC, and Eternal …
Vertex Cover (CVC) or Eternal Vertex Cover (EVC) is already a variant of VC, and Eternal …
A linear time algorithm for computing the eternal vertex cover number of cactus graphs
J Babu, V Prabhakaran, A Sharma - arXiv preprint arXiv:2005.08058, 2020 - arxiv.org
The eternal vertex cover problem is a dynamic variant of the classical vertex cover problem.
It is NP-hard to compute the eternal vertex cover number of graphs and known algorithmic …
It is NP-hard to compute the eternal vertex cover number of graphs and known algorithmic …
Spartan Bipartite Graphs Are Essentially Elementary
N Misra, SG Nanoti - arXiv preprint arXiv:2308.04548, 2023 - arxiv.org
We study a two-player game on a graph between an attacker and a defender. To begin with,
the defender places guards on a subset of vertices. In each move, the attacker attacks an …
the defender places guards on a subset of vertices. In each move, the attacker attacks an …
A new lower bound for eternal vertex cover number
J Babu, V Prabhakaran - arXiv preprint arXiv:1910.05042, 2019 - arxiv.org
We obtain a new lower bound for the eternal vertex cover number of an arbitrary graph $ G
$, in terms of the cardinality of a vertex cover of minimum size in $ G $ containing all its cut …
$, in terms of the cardinality of a vertex cover of minimum size in $ G $ containing all its cut …
Un nouveau modèle de protection de graphes: problème de l'ensemble de rebouclement éternel
N Dyab - 2023 - theses.hal.science
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 …
focusing on the concept of eternal feedback vertex sets. The problem of protecting a graph …