The burning number conjecture
on cat-constructs and trees with a single degree-2 vertex
M.L.A. van der Tol (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Y. Murakami β Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)
M. Keijzer β Graduation committee member (TU Delft - Electrical Engineering, Mathematics and Computer Science)
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
In the last decade the graph burning model was developed to model the spread of information between people. Graph burning is a process that is done in rounds with the aim of spreading information to every connected person in a network. Every round one new source of information may be appointed and information spreads from people who have received it, to all of their connections, just like fire spreads. The burning number of a graph, denoted by π(πΊ), is the parameter that quantifies the speed of this spread of information. It has been conjectured that the burning number for a connected graph on π vertices is at most ββπβ. We prove the burning number conjecture for cat-constructs. Cat-constructs are trees obtained from a path graph ππ by adding at most two vertices to subtrees of ππ. WeΒ show the burning sequence of a cat-construct may contain one fewer source than its burning number if the number of vertices for the cat-construct is more than the first square bigger than π. With this result