March 30: Good Friday (University Closed)

April 1: Easter Sunday (University Closed)

Anthony Bonato

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.

Important Dates

March 30: Good Friday (University Closed)

April 1: Easter Sunday (University Closed)

Upcoming Seminars

Colloquium talk:

**Hadrien Montanelli**:
*Pattern formation on the sphere*

Friday, March 23 at 14:30,
418 Machray Hall.

Rings and Modules seminar:

**T. Kucera**:
*Saturated Free Algebras and Almost Indiscernible Theories I*

Tuesday, March 27 at 14:40,
418 Machray Hall.

Rings and Modules seminar:

**T. Kucera**:
*Saturated Free Algebras and Almost Indiscernible Theories II*

Tuesday, April 3 at 14:40,
418 Machray Hall.

Colloquium talk:

**Jan Vonk**

Friday, April 6 at 14:30,
418 Machray Hall.