Graph Burning
on necklace graphs and cycle-forests
A.B. Kooijmans (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Yukihiro Murakami – Mentor (TU Delft - Discrete Mathematics and Optimization)
N.D. Verhulst – Mentor (TU Delft - Discrete Mathematics and Optimization)
E.G. Rens – Graduation committee member (TU Delft - Mathematical Physics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Graph burning is a process that models the spread of information through a network. This process is divided into rounds and is visualized as a spreading fire. Each round, a source of fire may be chosen from where the fire spreads and burns surrounding points. From every burned point, the fire propagates through adjacent points, eventually covering the entire network. The burning number of a graph, b(G), was introduced to measure the time required to burn the entire network.
It was proven that path graphs on n vertices have burning number ⌈√n⌉. It was then conjectured that all connected graphs have at most this burning number. The burning number has been estimated or identified for several classes of graphs. We provide a lower and upper bound for the burning number of a new class of graphs with a path-like structure, namely necklace graphs. Necklace graphs are constructed by concatenating smaller graphs, called pearls. To obtain bounds, we define lower-bound paths and upper-bound paths, which are paths connecting two designated vertices. We show that a lower-bound path always exists in the form of a shortest path, while finding an upper-bound path for an arbitrary necklace is NP-complete. For necklace graphs where a shortest path is an upper-bound path, we show that the burning number can take only two values.
Finally, we consider cycle-forests, which are disconnected graphs whose components are cycle graphs. We prove that burning cycle-forests is NP-complete.