Research Projects

Graphs are mathematical structures that represent pairwise relations between objects. Graphs are a common tool used to depict several situations such as social networks, transportation networks, internet and computer networks, etc. Graph protection or graph security games have their roots in the time of the ancient Roman Empire where people studied attack-defense strategies for actual warfare. A graph could be used to depict a situation where vertices could represent a set of safe houses or places, and the roads connecting them could be represented by edges. Depending on the situation, there could be a restriction on how the guards or soldiers can move from one place to another. The Eternal Vertex Cover is a two-player attack-defense game played on a graph. There is an n vertex graph and there are k guards. In each of their move, the first player (the attacker) attacks an edge. In response to the attack, the second player (the defender) moves a subset of guards to their neighbouring vertices such that at least one guard moves across the attacked edge. A guard cannot move for more than one step before the next attack. If after a finite sequence of attacks, the defender cannot make such a move, the attacker wins. The defender wins if they can protect the graph for an infinite sequence of attacks. The smallest number of guards with which the defender has a winning strategy is called the Eternal Vertex Cover Number of the graph G and is denoted by evc(G). A subset S of V (G) is said to be a vertex cover of G, if for every edge (u,v), either u is in S or v is in S, (or both). The size of a smallest vertex cover of the graph G is called the minimum vertex cover number of G, and is denoted by mvc(G). It is clear that the guards must form a vertex cover after every attack, otherwise, the attacker can attack the edge both of whose endpoints are unguarded, and win in the first move itself. In the game of Eternal Connected Vertex Cover, there is an additional constraint that the guards must always form a connected vertex cover, after each reconfiguration. The minimum number of guards required in this setting, for a graph G, is denoted by ecvc(G). The size of the smallest connected vertex cover of the graph G is denoted by cvc(G). It is clear that ecvc(G) is greater than or equal to cvc(G) by the same argument as above. It can also be seen that every vertex must belong to some minimum sized connected vertex cover, if ecvc(G)=cvc(G). In this project, we would like to explore whether the converse of the above statement is true or not. We describe this question in more detail in the objectives and expected outcome sections. We would also like to find out more about some structural parameters of graphs, related to the eternal vertex cover number of these graphs. We describe these parameters and their significance in the work methodology/research plan section and also in the objectives and expected outcome sections.