Burning Graphs

Faculty Member
Sean English

Project Image

Graph searching is a subfield of graph theory that seeks to understand how to efficiently explore a network. Graph burning is a discrete graph process that is performed as follows: The vertices are partitioned into ``burning'' vertices or ``non-burning'' vertices. If we say that the burning propagates, we mean that all non-burning neighbors of a burning vertex begin to burn. The burning number of a graph explores how many steps are necessary to cause all vertices in a graph to burn if on every step of the process a new vertex is chosen to be burning (this is called a source), and then the fire propagates from all previously burning vertices. There are many open questions we can explore involving burning numbers. We will consider the burning numbers of some specific classes of graphs and if there is time, we will attempt to attach the Burning Number Conjecture, which states that any graph on n vertices has burning number at most the ceiling of n^{1/2}.

Team Meetings
Project Difficulty
Undergrad Prerequisites

Graph Theory is required, combinatorics is preferred.