The burning number conjecture

on cat-constructs and trees with a single degree-2 vertex

Bachelor thesis (2024)

Authors

M.L.A. van der Tol Electrical Engineering, Mathematics and Computer Science

Contributors

Yukihiro Murakami Discrete Mathematics and Optimization - EEMCS (mentor)
M. Keijzer Mathematical Physics - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science
More Info
expand_more

Published Date

28-08-2024

Language

English

Reuse Rights

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

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

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.