SFU Discrete Math Seminar: Sebastian Gonzalez

  • Date: 11/08/2016
Speaker(s):
Sebastian Gonzalez, SFU
Location: 

Simon Fraser University

Topic: 

Cops and Robbers on Oriented Grids II

Description: 

"Cops and Robbers" is a well-known pursuit game played on a graph. There are two players, one controls the cops and the other controls the robber, who take turns moving along edges of the graph. The goal of the cops is to capture the robber, which is accomplished if a cop occupies the same vertex as the robber. The main question about this game is to determine the cop number of a graph G, which is the minimum number of cops that can guarantee the robber's capture on G. This problem has been widely studied for the case of undirected graphs, but there is almost no work done about the game played on directed graphs. Recently, Hosseini and Mohar determined the cop number for some families of orientations of a grid on the torus. In this talk we will present bounds for the cop number for a more general family of orientations of this grid.

Other Information: 

Location: SFU K 9509

 

This seminar is an on-going activity for the CRG on Applied Combinatorics.