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 ma
...
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
we show that adding a vertex as a leaf to these cat-constructs and appointing it as a source results in the proof of the burning number conjecture for certain 3-caterpillars. Furthermore we prove the burning number conjecture holds for trees with a single degree-2 vertex.
