Upper Bound on the Burning Number of Graphs

Overview

The burning number of a graph was introduced by Bonato-Janssen-Roshanbin [Lecture Notes in Computer Science 8882 (2014)] for measuring the speed of the spread of contagion in a graph. Today, mathematicians are using graphs to model social networks ranging from facebook users to a population of deer in a forest. The burning number of a graph is used as a simplistic model for the spread of contagion along social networks. For example, the spread of a virus through a species population via contact or the spread of a forest fire among trees can be modeled by the burning number of a graph. In their paper, Bonato-Janssen-Roshanbin considered a graph process which they called burning. At the beginning of the process, all vertices of a graph are unburned. During each round, one may choose an unburned vertex and change its status to burned. At the same time, each of the vertices that are already burned, will remain burned and spread to all of its neighbors and change their status to burned. A graph is called k-burnable if it can be burned in at most k steps. The burning number of a graph G, denoted by b(G), is the minimum number of rounds necessary to burn all vertices of the graph. They conjectured the burning number of any connected graph G on n vertices is at most the square root of n, denoted by sqrt(n). The previously best known upper bound was roughly 1.298*sqrt(n). In this paper, we improved the upper bound to roughly 1.225*sqrt(n) by a novel method of induction.

Awards (1)

• American Mathematical Society: Certificate of Honorable Mention

Competition history

• ISEF 2017 Mathematics · Entry MATH031

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.