Hypergraph burning

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

[img] [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)


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.

Item Type: Thesis (Masters)
URI: http://research.library.mun.ca/id/eprint/16214
Item ID: 16214
Additional Information: Includes bibliographical references (pages 90-92)
Keywords: combinatorics, graph theory, hypergraph theory, design theory, pursuit-evasion games, graph searching
Department(s): Science, Faculty of > Mathematics and Statistics
Date: February 2023
Date Type: Submission
Digital Object Identifier (DOI): https://doi.org/10.48336/1WPS-BH93
Library of Congress Subject Heading: Combinatorial analysis; Graph theory; Influence (Psychology)-- Mathematical models; Computational complexity

Actions (login required)

View Item View Item


Downloads per month over the past year

View more statistics