On The Eternal Vertex Cover Number Of Maximal Outerplanar Graphs

Abstract

This thesis presents the results of our investigation on the eternal vertex cover newlineproblem in maximal outerplanar graphs. A vertex cover in a graph G(V,E) is a newlinesubset S and#8838; V such that for every edge in E, at least one of its endpoints is in S. The newlinecardinality of a minimum vertex cover of G is denoted by vc(G). Intuitively, if newlinewe imagine that a guard placed on a vertex v can monitor all edges incident at v, newlinethen vc(G) is the minimum number of guards required to ensure surveillance of newlineevery edge in G. The eternal vertex cover problem, introduced by Klostermeyer newlineand Mynhardt in 2009 [1], generalizes the vertex cover problem to the context of newlinedynamic surveillance of the edges of a given graph G, and is commonly stated as newlinean attacker defender game on G. Guards are initially placed by the defender on a newlinesubset of vertices of G, such that: newline1. for each edge e and#8712; E(G), there is a guard on at least one of the end points (i.e., newlinethe positions where the guards are placed must form a vertex cover of G) and, newline2. at most one guard is placed on a vertex. newlineOn each round, the attacker chooses an edge to attack. In response, the defender newlineis permitted to move one or more guards, from the present vertex to an adjacent newlinevertex, satisfying (a) at least one guard must move across the attacked edge and newline(b) constraints (1) and (2) above continue to hold after the movement. All guard newlinemovements of a round are assumed to happen in parallel. After each round of attack newlineand defense, the game proceeds to the next round of attack-defense. The defense is newlinesuccessful if any arbitrary sequence of attacks, starting from the initial position can newlinebe defended; i.e., sequences of attacks can be defended eternally.