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 n≥3 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.