Anthony Bonato

(Department of Mathematics, Ryerson)

Burning spiders and path forests

Date: Friday, November 24, 2017

Graph burning is a simplified model for the spread of memes and contagion in social networks. A fire breaks out in each time-step and spreads to its neighbours. The burning number of a graph measures the number of time-steps it takes so that all vertices are burning. While it is conjectured that the burning number of a connected graph of order n is a most the ceiling of the square root of n, this remains open in general.

We prove the conjectured bound for spider graphs, which are trees with exactly one vertex of degree at least 3. To prove our result for spiders, we develop new bounds on the burning number for path-forests, which in turn leads to a 3/2-approximation algorithm for computing the burning number of path-forests.

Upcoming Seminars

Graduate Student seminar:
Daniel Johnson: Mathematics and the Natural Sciences
Thursday, January 18 at 14:30, 208 Armes.

Graduate Student seminar:
Kyrylo Muliarchyk
Thursday, January 18 at 15:00, 208 Armes.

Graduate Student seminar:
Sahar Rahimzad Lamey
Thursday, January 25 at 14:30, 208 Armes.

Graduate Student seminar:
Babak Irandoust-Azar
Thursday, January 25 at 15:00, 208 Armes.