Anthony Bonato

(Department of Mathematics, Ryerson)

Burning spiders and path forests

Date: Friday, November 24, 2017
Time: 15:30
Location: 418 Machray Hall

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

Rings and Modules seminar:
R. W. Quackenbush: When is a \(\vee\)-semilattice a lattice?
Tuesday, November 21 at 14:40, 418 Machray Hall.

Functional Analysis seminar:
Edward Timko: A Classification of \(n\)-tuples of Commuting Isometries
Tuesday, November 21 at 15:00, 205 Armes.

Geometry and Topology seminar:
Marc Ethier
Friday, November 24 at 13:30, 316 Machray Hall.

Combinatorics seminar:
Anthony Bonato: Burning spiders and path forests
Friday, November 24 at 15:30, 418 Machray Hall.