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 x1,...,xk such that for every vertex u of G, there is some i∈{1,...,k} with distG(u,xi) ≤ k-i, and distG(xi,xj) ≥ 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 n2 vertices of degree 2, and n3 vertices of degree at least 3, we show

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