**Supervisor:** Dr. Anthony Bonato, Ryerson University

**Project Overview**

In graph searching, we consider simplified, combinatorial models for the detection or neutralization of an adversary's activity on a network. The most studied such game is Cops and Robbers, where the cops attempt to capture the robber by prescribed rules. We will consider a new variant of Cops and Robbers called the localization game, where the robber is invisible but we have partial information on its whereabouts. We will study the localization game on graphs derived from combinatorial designs and models for social networks.

**Detailed Description**

In graph searching, we consider simplified, combinatorial models for the detection or neutralization of an adversary's activity on a network. Such models often focus on vertex-pursuit games, where agents or cops are attempting to capture an adversary or robber loose on the vertices of a network. The players move at alternating ticks of the clock and have restrictions on their movements or relative speed depending on the type of game played. The most studied such game is Cops and Robbers, where the cops and robber can only move to vertices with which they share an edge. The minimum number of cops needed to capture the robber in a graph G is the cop number of G, written c(G). Cops and Robbers and its variants form an emerging topic in graph theory, with new results rapidly appearing in the literature.

The localization game played on graphs is a variant of Cops and Robbers, where the robber is invisible, but the cops may send distance probes that return the graph distance from their position to the robber. The localization game is motivated by real-world tracking problems such as pinpointing cell phone users via mobile receivers. The cops may move to any vertex of the graph each round, while the robber moves from vertex-to-vertex along edges. The cops win if they can determine the exact position of the robber; otherwise, the robber wins. Placing cops on each vertex ensures a win for the cops, so we may define the localization number of G, written ζ(G), to be the least integer for which the cops have a winning strategy over any possible strategy of the robber (that is, we consider the worst-case that the robber a priori knows the entire strategy of the cops.

There is a small but rapidly growing set of results on the localization number. Previous work has shown that ζ(G) is bounded above by the pathwidth of G and that the localization number is unbounded even on graphs obtained by adding a universal vertex to a tree. Computing ζ(G) is NP-hard for graphs with diameter 2. Connections have been found between the localization number and the chromatic number, and the parameter has been studied for outerplanar graphs and hypercubes.

The localization number of the incidence graphs of designs was studied by Bonato and others. In particular, they gave exact values for the localization number of the incidence graphs of projective and affine planes, and bounds for the incidence graphs of Steiner systems and transversal designs. An interesting problem to explore is to consider the localization number for graphs derived from Latin Squares. What bounds or exact values for ζ(G) can be found for such graphs? The problem is sufficiently open-ended to allow for many partial results and would require only elementary methods from Latin squares and combinatorial designs. My post-doc Trent Marbach is an expert on Latin squares and will help guide this research.

Another direction is to consider the localization number for models of social networks. In 2004, I introduced the Iterated Local Transitivity (ILT) model, which provably simulates many of the properties observed in social networks, such as the small-world property, densification, and bad spectral clustering. The ILT model is deterministic and straightforward to define, but leads to complicated graph dynamics. The model replicates the graph structure of an initial graph over discrete time-steps. A good problem with an achievable solution would be to analyze the localization number in the ILT model, relating it back to the localization number of the initial graph. Variants of the ILT model exist for directed graphs and hypergraphs, and a broader goal would be to analyze the localization number and related parameters for such variants.