11 papers
On Eternal Connected Vertex Cover
Rajat Adak, Saraswati Girish Nanoti
For a connected graph with at least one edge, the \textit{eternal connected vertex cover} number is the minimum number of guards that can maintain a connected vertex…
Structural and computational aspects of majority coloring games
Yash Chawda, Saraswati Girish Nanoti, Brahadeesh Sankarnarayanan +1
A majority coloring of a graph is a coloring of such that, for each vertex , the number of neighbors of with the same color as is at most .…
On the majority game chromatic number of forests and other graphs
Yash Chawda, Saraswati Girish Nanoti, Brahadeesh Sankarnarayanan
A majority coloring of a graph is a vertex coloring of in which no vertex has more than half of its neighbors colored with its own color. The least number of colors require…
Off-diagonal Rado numbers for and
Rajat Adak, Yash Bakshi, L. Sunil Chandran +1
The study of Ramsey-type problems for linear equations originated with Schur's theorem and was later placed in a systematic framework by Richard Rado. In the off-diagonal setting,…
Off-diagonal Rado number for and
Rajat Adak, Yash Bakshi, L. Sunil Chandran +1
Ramsey-type problems for linear equations began with Schur's theorem and were systematically generalized by Richard Rado. In the off-diagonal framework for two colors, one consider…
m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
Tiziana Calamoneri, Federico Corò, Neeldhara Misra +2
We study the m-Eternal Domination problem, which is the following two-player game between a defender and an attacker on a graph: initially, the defender positions k guards on verti…
On a Characterization of Spartan Graphs
Neeldhara Misra, Saraswati Girish Nanoti
The eternal vertex cover game is played between an attacker and a defender on an undirected graph . The defender identifies vertices to position guards on to begin with. The…
Revisiting Token Sliding on Chordal Graphs
Rajat Adak, Saraswati Girish Nanoti, Prafullkumar Tale
In this article, we revisit the complexity of the reconfiguration of independent sets under the token sliding rule on chordal graphs. In the \textsc{Token Sliding-Connectivity} pro…
A Little Aggression Goes a Long Way
Jyothi Krishnan, Neeldhara Misra, Saraswati Girish Nanoti
Aggression is a two-player game of troop placement and attack played on a map (modeled as a graph). Players take turns deploying troops on a territory (a vertex on the graph) until…
Spartan Bipartite Graphs are Essentially Elementary
Neeldhara Misra, Saraswati Girish Nanoti
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 e…
Eternal Vertex Cover on Bipartite and Co-Bipartite Graphs
Neeldhara Misra, Saraswati Nanoti
Eternal Vertex Cover problem is a dynamic variant of the vertex cover problem. We have a two player game in which guards are placed on some vertices of a graph. In every move, one…