|Date:||Friday, November 24, 2017|
|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.
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:
Friday, November 24 at 13:30, 316 Machray Hall.