5 papers · 1 filter
Token sliding independent set reconfiguration on block graphs
Mathew C. Francis, Veena Prabhakaran
Let be an independent set of a simple undirected graph . Suppose that each vertex of has a token placed on it. The tokens are allowed to be moved, one at a time, by slid…
Eternal vertex cover number of maximal outerplanar graphs
Jasine Babu, K. Murali Krishnan, Veena Prabhakaran +1
Eternal vertex cover problem is a variant of the classical vertex cover problem modeled as a two player attacker-defender game. Computing eternal vertex cover number of graphs is k…
A Linear Time Algorithm for Computing the Eternal Vertex Cover Number of Cactus Graphs
Jasine Babu, Veena Prabhakaran, Arko Sharma
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 algorithmi…
A new lower bound for eternal vertex cover number
Jasine Babu, Veena Prabhakaran
We obtain a new lower bound for the eternal vertex cover number of an arbitrary graph , in terms of the cardinality of a vertex cover of minimum size in containing all its c…
On Graphs whose Eternal Vertex Cover Number and Vertex Cover Number Coincide
Jasine Babu, L. Sunil Chandran, Mathew Francis +3
The eternal vertex cover problem is a variant of the classical vertex cover problem where a set of guards on the vertices have to be dynamically reconfigured from one vertex cover…