Burning a Graph

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₁,...,x_k such that for every vertex u of G, there is some i∈{1,...,k} with dist_G(u,x_i) ≤ k-i, and dist_G(x_i,x_j) ≥ j-i  for every i,j∈{1,...,k}.

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

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₂ vertices of degree 2, and n_≥3 vertices of degree at least 3, we show

b(T) ≤ ⌈√(n+n₂+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.

3.