Graph Burning

Abstract

Graph burning models the transmission of viruses and information. Graph burning is an iterative process in which vertices go from unburned to burned. In every round, first, all neighbors of burned vertices are also burned, second, one unburned vertex is selected as a source and also burned. These rounds are repeated until every vertex is burned. The burning number of a graph is the minimum number of rounds needed to burn every vertex in that graph.

Finding the burning number for a general graph is an NP-complete problem. Therefore, computing the burning number for relatively big graphs takes a long time. One way to reduce this time is by finding lower and upper bounds for the burning number that are close to the actual burning number.

In this thesis, we find lower and upper bounds for the burning number of Cartesian and strong products of multiple path graphs. These graphs are also known as higher-dimensional grid and king's graphs. The technique used to find these bounds is based on the technique Mitsche et al. used to asymptotically determine the burning number of grid graphs and king's graphs. A grid graph is the Cartesian product of two path graphs and a king's graph is the strong product of two path graphs.

For the burning number of higher-dimensional grid graphs, we found an implicit lower bound. The lower bound for the burning number of an i-dimensional grid graph can be calculated using the lower bound for the burning number of the (i-1)-dimensional grid graph.

We found that the burning number of the strong product of i paths of length n is larger than 0.5n^i/(i+1) and smaller than ⌈0.5(n+1)⌉. For the strong product of i paths of lengths m₁,m₂,…,m_i, we proved the burning number is larger than 0.5∏ⁱ_j=1m_j^1/(i+1).