Grant: Discovery Grants Program - Individual

In mathematics, a graph G consists of two sets, V and E, where the elements of V are called vertices, and the elements of E are pairs of vertices called edges. I am interested in a graph searching game called sweeping. In sweeping, an invisible intruder is loose in the graph, and some number of sweepers need to move through the graph and capture the intruder. An interesting question that arises is: how few sweepers are needed to catch the intruder? Determining this number is difficult, so my research looks for bounds on this number. If we imagine that the graph represents a real-world object like a computer network, then the intruder could be a virus, and catching the intruder would correspond to removing all viruses from the system. Sweeping is often looked at as a problem in network security, and as such is applicable to many real-world problems that can be of major importance to Canadians as well as to national and international companies. I am also interested in graph problems involving breaking up the edge set E into identical subgraphs. These are known as graph decomposition problems. I'm particularly interested in Hamilton decompositions. These are decompositions where each of the identical subgraphs is a cycle with as many vertices as the original graph.