Ryan Martin

Vertex identifying codes in infinite grids
Abstract: In a graph, a code C is simply a subset of the vertex set and we say that C is ``vertex-identifying'' if the intersection of N[v] with C is unique and nonempty, where N[v] is the closed neighborhood of vertex v. In general, the code is ``r-vertex-identifying'' if the ball of radius r intersected with C is unique and nonempty for every vertex v.

Much of the literature of vertex-identifying codes is devoted to finding the minimum density (defined in a natural way) of a code on an infinite grid. Of particular interest are the square grid, the hexagonal grid and the so-called king grid. In this talk, we will discuss the applications of this graph invariant as well as the infinite square and hexagonal grid and an application of the discharging method. We will also discuss a connection between vertex-identifying codes and the more well-studied Hamming codes. This is joint work with Brendon Stanton, Iowa State University.