Bounds on the burning number. (English) Zbl 1375.05192
Summary: Motivated by a graph theoretic process intended to measure the speed of the spread of contagion in a graph, A. Bonato et al. [Lect. Notes Comput. Sci. 8882, 13–22 (2014; Zbl 1342.05154)] define the burning number \(b(G)\) of a graph \(G\) as the smallest integer \(k\) for which there are vertices \(x_1,\ldots,x_k\) such that for every vertex \(u\) of \(G\), there is some \(i\in\{1,\ldots,k\}\) with \(\operatorname{dist}_G(u,x_i)\leq k-i\), and \(\operatorname{dist}_G(x_i,x_j)\geq j-i\) for every \(i,j\in\{1,\ldots,k\}\).
For a connected graph \(G\) of order \(n\), they prove that \(b(G)\leq 2\lceil\sqrt{n}\rceil-1\), and conjecture \(b(G)\leq\lceil\sqrt{n}\rceil\). We show that \(b(G)\leq\sqrt{\frac{32}{19}\cdot\frac{n}{1-\epsilon}}+\sqrt{\frac{27}{19\epsilon}}\) and \(b(G)\leq\sqrt{\frac{12n}{7}}+3\approx 1.309\sqrt{n}+3\) for every connected graph \(G\) of order \(n\) and every \(0<\epsilon<1\). For a tree \(T\) of order \(n\) with \(n_2\) vertices of degree 2, and \(n_{\geq3}\) vertices of degree at least 3, we show \(b(T)\leq\lceil\sqrt{(n+n_2)+\frac{1}{4}}+\frac{1}{2}\rceil\) and \(b(T)\leq\lceil\sqrt{n}\rceil+n_{\geq3}\). Furthermore, we characterize the binary trees of depth \(r\) that have burning number \(r+1\).
For a connected graph \(G\) of order \(n\), they prove that \(b(G)\leq 2\lceil\sqrt{n}\rceil-1\), and conjecture \(b(G)\leq\lceil\sqrt{n}\rceil\). We show that \(b(G)\leq\sqrt{\frac{32}{19}\cdot\frac{n}{1-\epsilon}}+\sqrt{\frac{27}{19\epsilon}}\) and \(b(G)\leq\sqrt{\frac{12n}{7}}+3\approx 1.309\sqrt{n}+3\) for every connected graph \(G\) of order \(n\) and every \(0<\epsilon<1\). For a tree \(T\) of order \(n\) with \(n_2\) vertices of degree 2, and \(n_{\geq3}\) vertices of degree at least 3, we show \(b(T)\leq\lceil\sqrt{(n+n_2)+\frac{1}{4}}+\frac{1}{2}\rceil\) and \(b(T)\leq\lceil\sqrt{n}\rceil+n_{\geq3}\). Furthermore, we characterize the binary trees of depth \(r\) that have burning number \(r+1\).
MSC:
05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
05C12 | Distance in graphs |
Citations:
Zbl 1342.05154References:
[1] | S. Bessy, A. Bonato, J. Janssen, D. Rautenbach, E. Roshanbin, Burning a graph is hard, Discrete Appl. Math. http://dx.doi.org/10.1016/j.dam.2017.07.016; S. Bessy, A. Bonato, J. Janssen, D. Rautenbach, E. Roshanbin, Burning a graph is hard, Discrete Appl. Math. http://dx.doi.org/10.1016/j.dam.2017.07.016 · Zbl 1372.05214 |
[2] | S. Bessy, D. Rautenbach, Bounds, approximation, and hardness for the burning number, arXiv:1511.06023; S. Bessy, D. Rautenbach, Bounds, approximation, and hardness for the burning number, arXiv:1511.06023 · Zbl 1371.05073 |
[3] | Bonato, A.; Janssen, J.; Roshanbin, E., Burning a graph as a model of social contagion, Lecture Notes in Comput. Sci., 8882, 13-22 (2014) · Zbl 1342.05154 |
[4] | Bonato, A.; Janssen, J.; Roshanbin, E., How to burn a graph, Internet Math., 12, 85-100 (2016) · Zbl 1461.05193 |
[5] | A. Bonato, J. Janssen, E. Roshanbin, Burning a graph is hard, arXiv:1511.06774; A. Bonato, J. Janssen, E. Roshanbin, Burning a graph is hard, arXiv:1511.06774 · Zbl 1372.05214 |
[6] | Diestel, R., Graph Theory (2010), Springer · Zbl 1218.05001 |
[8] | Meir, A.; Moon, J. W., Relations between packing and covering numbers of a tree, Pacific J. Math., 61, 225-233 (1975) · Zbl 0315.05102 |
[9] | Roshanbin, E., Burning a Graph as a Model of Social Contagion (2016), Dalhousie University, (Ph.D. thesis) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.