Bounds on the Burning Number

2015/11/18 by Bessy, Stéphane, Bonato, Anthony, Janssen, Jeannette +1 · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1511.06023

Abstract

Motivated by a graph theoretic process intended to measure the speed of the spread of contagion in a graph, Bonato, Janssen, and Roshanbin [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 \rm dist_G(u,x_i)≤ k-i, and \rm dist_G(x_i,x_j)≥ j-i for every i,j∈ \ 1,…,k\. For a connected graph G of order n, they prove that b(G)≤ 2\lceil√(n)\rceil-1, and conjecture b(G)≤ \lceil√(n)\rceil. We show that b(G)≤ √((32)/(19)⋅ (n)/(1-ε))+√((27)/(19ε)) and b(G)≤ √((12n)/(7))+3≈ 1.309 √(n)+3 for every connected graph G of order n and every 0

Cited by

• The burning number conjecture holds for trees of order n with at most \lfloor √(n-1)\rfloor degree-2 vertices
• Random burning of the Euclidean lattice

Related

• An Upper Bound on Burning Number of Graphs
• The Burning Number Conjecture Holds Asymptotically
• Burning a binary tree and its generalization
• The Graph Burning Conjecture is true for trees without degree-2 vertices
• An improved bound on the burning number of graphs