Hypergraph burning

Jones, Caleb (2023) Hypergraph burning. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (864kB)

Abstract

Graph burning is a combinatorial game or process that models the spread of in uence throughout a network. We introduce a generalization of graph burning which applies to hypergraphs. One of our key results is that arbitrary hypergraphs do not satisfy a bound analogous to the one in the Burning Number Conjecture. We also introduce a variant called \lazy" hypergraph burning, along with a new parameter, the lazy burning number. Interestingly, lazily burning a graph is trivial, while lazily burning a hypergraph can be quite complicated. Moreover, the lazy burning model is a useful tool for analyzing the roundbased model. We obtain bounds on the burning number and lazy burning number of a hypergraph in terms of its parameters, as well as stronger bounds that apply to Steiner triple systems. We also discuss the complexity of both the round-based and lazy models. Finally, we introduce two further variants of (lazy) hypergraph burning.

Actions (login required)

View Item