#### Title

Upper Bound on the Burning Number of Graphs

#### School Name

Dutch Fork High School

Mathematics

Mentored

#### Mentor

Mentor: Linyuan Lu, University of South Carolina

1st Place

2nd Place

#### Abstract

The burning number of a graph was introduced by Bonato-Janssen-Roshanbin [Lecture Notes in Computer Science 8882 (2014)]. It is used to model the spread of contagion processes over contact networks. For example, many graphs are used to model social connections on facebook or a population of trees in the wilderness. The burning number of a graph would estimate the amount of time it would take information to travel among facebook friends, or the time it would take for a virus to infect an entire population of trees. 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.

Wall 205

#### Start Date

3-25-2017 10:45 AM

Oral and Written

#### Group Project

No

COinS

Mar 25th, 10:45 AM

Upper Bound on the Burning Number of Graphs

Wall 205

The burning number of a graph was introduced by Bonato-Janssen-Roshanbin [Lecture Notes in Computer Science 8882 (2014)]. It is used to model the spread of contagion processes over contact networks. For example, many graphs are used to model social connections on facebook or a population of trees in the wilderness. The burning number of a graph would estimate the amount of time it would take information to travel among facebook friends, or the time it would take for a virus to infect an entire population of trees. 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.