voltarData: 26/09/2015
Título: Burning a Graph
Palestrante: Prof. Dr. Dieter Rautenbach, Universität Ulm
Data: 26 de novembro de 2015, 13h
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.
(como essa descrição tem fórmula, favor olhar em: http://www.pgmat.uff.br/index.php/p-visitantes/46-palestra20151125)
Confira aqui a apresentação