Upper Bound on the Burning Number of Graphs

School Name

Dutch Fork High School

Grade Level

12th Grade

Presentation Topic

Mathematics

Presentation Type

Mentored

Mentor

Mentor: Linyuan Lu, University of South Carolina

Oral Presentation Award

1st Place

Written Paper Award

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.

Location

Wall 205

Start Date

3-25-2017 10:45 AM

Presentation Format

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.