Simon Zheng '13

Title: Pegging Numbers of Strongly Regular Graphs and Grid Graphs

Problem: What is the minimum number pegs required to reach the entire vertex set of different classes of graphs?

Mentor: Padraic Bartlett, California Institute of Technology

Activities and Interests: Math Team, Varsity Soccer, French Club

Abstract: This research studies the mathematical game of graph pegging, which has applications related to modeling network flow, transportation, and supply chain problems in computer science and economics. In graph pegging, we place at most one peg in each vertex of a graph. Given two adjacent pegs and an empty vertex adjacent to the second peg, a pegging move consists of jumping the first peg over the second peg into the empty vertex. The second peg is then removed. We define the pegging number of a graph as the minimum number of pegs such that starting from any distribution of that size, every vertex can be reached with pegging moves. Similarly, we define the optimal pegging number as the minimum number of pegs such that there exists at least one distribution of that size for which every vertex can be reached. We characterize strongly regular graphs with optimal pegging number 2 and 3. In addition, we compute the pegging number and optimal pegging number of the 2 x n grid graph. Finally, we compute the optimal pegging number of the 3 x n grid graph. Overall, we successfully derived the pegging numbers of two classes of graphs.