Degree-Constrained Graph Burning

None, None

Degree-Constrained Graph Burning

Extremal Bounds, Regular Constructions, and 𝛼-Angular Trees

Master Thesis (2026)

Author(s)

M.J.P. Reinders (TU Delft - Electrical Engineering, Mathematics and Computer Science)

Contributor(s)

Y. Murakami – Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)

N.D. Verhulst – Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)

D.C. Gijswijt – Graduation committee member (TU Delft - Electrical Engineering, Mathematics and Computer Science)

R. Versendaal – Graduation committee member (TU Delft - Electrical Engineering, Mathematics and Computer Science)

Faculty

Electrical Engineering, Mathematics and Computer Science

Graph Burning Extremal Graph Theory Burning Number Regular Graphs 𝛼-Angular Trees Necklace Graphs

To reference this document use

https://resolver.tudelft.nl/uuid:c72a1080-1649-4521-afba-8f479fd2aa29

More Info

expand_more

Publication Year

2026

Language

English

Graduation Date

11-05-2026

Awarding Institution

Delft University of Technology

Programme

Applied Mathematics

Faculty

Electrical Engineering, Mathematics and Computer Science

Downloads counter

44

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.

Abstract

Graph burning is a discrete-time process on a graph that models the spread of information or influence. At each time step, an unburned vertex may be chosen as a source of fire, after which the fire spreads from previously burned vertices to their neighbors. The minimum number of time steps required to burn all vertices is called the burning number 𝑏(𝐺) of a graph 𝐺.

In many applications, networks are subject to capacity limitations, such as a bounded number of connections per vertex. We study degree-constrained graphs and their extremal behavior.

For connected graphs of bounded maximum degree Δ and a fixed burning number 𝑏, we determine the maximum possible order. We show that this bound is of order 𝒪(Δ𝑏−1). We also show that this bound is tight via explicit constructions, which yields a logarithmic lower bound of the form 𝑏(𝐺) ≥ Ω(log_(Δ−1) 𝑛). We further show a more narrow bound in the 𝑑-regular setting and prove this is also tight via explicit constructions.

We further consider the complementary problem of constructing 𝑑-regular graphs with large burning numbers. We introduce the family of 𝑑-necklaces and show that their burning numbers match the known asymptotic upper bound of Martinsson up to an additive constant of one. These graphs also achieve the corresponding upper bound for the radius of Kim et al. up to an additive constant of one.

Finally, for restricted tree classes, we obtain improved asymptotic upper bounds on the burning number by adapting an existing framework. One consequence is an asymptotic refinement by a factor of 1/√2 of the known bound for homeomorphically irreducible trees of Murakami.

Files

Master_Thesis_-_MJP_Reinders_-... (pdf)

(pdf | 0.341 Mb)

License info not available