**Palestrante:** Prof. Dieter Rautenbach, Universität Ulm.

**Nova Data: 26 de novembro de 2015, 13h**

**Novo Local: IME, Campus Gragoatá, Sala 407**

**Resumo: **Motivated by a graph theoretic process intended to measure the speed of the spread of contagion in a graph, Bonato et al. [Burning a Graph as a Model of Social Contagion, Lecture Notes in Computer Science 8882 (2014) 13-22] define the burning number *b(G)* of a graph *G* as the smallest integer *k* for which there are vertices *x _{1},...,x_{k}* such that for every vertex

For a connected graph *G* of order *n*, they prove *b(G) ≤ *⌈√*n*⌉* -1*, and conjecture *b(G) ≤ *⌈√

*b(G) ≤ √(32/19·n/(1-ε)) + √(27/(19ε))*

*b(G) ≤ √(12n/7)+3 ≈ 1.309 √n+3*

for every connected graph *G* of order *n* and every 0<*ε*<1. For a tree *T* of order *n* with *n _{2}* vertices of degree

*b(T) ≤ *⌈*√(n+n _{2}+1/4) + 1/2*⌉

*b(T) ≤ *⌈*√n*⌉* + n _{≥3}*

Finally, we show that the problem of deciding whether *b(G) ≤ k* for a given graph *G* and a given integer *k* is NP-complete even when restricting the graphs *G* to either the unions of paths or to trees that have exactly one vertex of degree at least *3*.

The presented results are joint work with Stephane Bessy.