Search

Abstract: Perfect vertex elimination schemes are part of the characterizations for several classes of graphs, including chordal and cop-win. Partial elimination schemes reduce a graph to an important subgraph, for example, -cores and robber-win graphs. We are interested in those partial elimination schemes, in which once a vertex is ready to be eliminated, it stays in that state regardless of which other vertices are eliminated. We show that in such a scheme, the sets of subsets of eliminated vertices, when ordered by inclusion, form an upper locally distributed lattice. We also show that (a) unless they contain a specific induced subgraph, the cop-win orderings have this property, and that (b) the process of cleaning graphs also leads to upper locally distributed lattices. Finally, we ask for an elimination scheme, which graphs are associated with distributive lattices? [Copyright &y& Elsevier]

Abstract: Following the decontamination metaphor for searching a graph, we introduce a cleaning process, which is related to both the chip-firing game and edge searching. Brushes (instead of chips) are placed on some vertices and, initially, all the edges are dirty. When a vertex is ‘fired’, each dirty incident edge is traversed by only one brush, cleaning it, but a brush is not allowed to traverse an already cleaned edge; consequently, a vertex may not need degree-many brushes to fire. The model presented is one where the edges are continually recontaminated, say by algae, so that cleaning is regarded as an on-going process. Ideally, the final configuration of the brushes, after all the edges have been cleaned, should be a viable starting configuration to clean the graph again. We show that this is possible with the least number of brushes if the vertices are fired sequentially but not if fired in parallel. We also present bounds for the least number of brushes required to clean graphs in general and some specific families of graphs. [Copyright &y& Elsevier]

We consider a variant of the pursuit–evasion game Cops and Robber, called Zombies and Survivors. The zombies, being of limited intelligence, have a very simple objective at each round: move closer to a survivor. The zombies capture a survivor if one of the zombies moves onto the same vertex as a survivor. The survivor’s objective is to avoid capture for as long as possible, hopefully indefinitely. Because there may be multiple geodesics, or shortest paths, joining a zombie and its nearest survivor, the game can be considered from a probabilistic or deterministic approach. In this paper, we consider a deterministic approach to the game. In particular, we consider the worst case for the survivors; whenever the zombies have more than one possible move, they choose one that works to their advantage. This includes choice of initial position, and choosing which geodesic to move along if more than one is available. In other words, the zombies play intelligently, subject to the constraint that each zombie must move along a geodesic between itself and the nearest survivor. The zombie number of a graph G is the minimum number of zombies required to capture the survivor on G . We determine the zombie number for various graphs, examine the relationship between the zombie number and cop number of a graph, and describe some distinctions from Cops and Robber. [ABSTRACT FROM AUTHOR]

We consider a variation of the Cops and Robber game where the cops can only see the robber when the distance between them is at most a fixed parameter ℓ. We consider the basic consequences of this definition for some simple graph families, and show that this model is not monotonic, unlike common models where the robber is invisible. We see that cops' strategy consists of a phase in which they need to "see" the robber (move within distance ℓ of the robber), followed by a phase in which they capture the robber. In some graphs the first phase is the most resource intensive phase (in terms of number of cops needed), while in other graphs, it is the second phase. Finally, we characterize those trees for which k cops are sufficient to guarantee capture of the robber for all ℓ ≥ 1. [ABSTRACT FROM AUTHOR]

We introduce a new variant of the game of Cops and Robbers played on graphs, where the robber is invisible unless outside the neighbor set of a cop. The hyperopic cop number is the corresponding analogue of the cop number, and we investigate bounds and other properties of this parameter. We characterize the cop-win graphs for this variant, along with graphs with the largest possible hyperopic cop number. We analyze the cases of graphs with diameter 2 or at least 3, focusing on when the hyperopic cop number is at most one greater than the cop number. We show that for planar graphs, as with the usual cop number, the hyperopic cop number is at most 3. The hyperopic cop number is considered for countable graphs, and it is shown that for connected chains of graphs, the hyperopic cop density can be any real number in [ 0 , 1 / 2 ]. [ABSTRACT FROM AUTHOR]