Virgélot Virgile

Topic

Mobile Guards’ Strategies for Graph Surveillance and Protection

Department of Mathematics and Statistics

Date & location

• Tuesday, February 13, 2024
• 8:30 A.M.
• Virtual Defence

Examining Committee

Supervisory Committee

• Dr. Gary MacGillivray, Department of Mathematics and Statistics, University of Victoria (Co-Supervisor)
• Dr. Kieka Mynhardt, Department of Mathematics and Statistics, UVic (Co-Supervisor)
• Dr. Sajin Koroth, Department of Computer Science, UVic (Outside Member)

External Examiner

• Prof. Jan H van Vuuren, Department of Industrial Engineering, Stellenbosch University

Chair of Oral Examination

• Dr. Michael McGuire, Department of Electrical and Computer Engineering, UVic

Abstract

In this dissertation, we study the “one guard moves” model of both the eternal domination game and the eviction game.

We investigate the computational complexity of deciding whether 𝑘 guards can respond to any sequence of attacks on an 𝑛-vertex graph 𝐺 in both games. We show that this decision problem is EXPTIME-complete when neither 𝐺 nor 𝑘 is fixed, and when the initial configuration of the guards is given. We further show that in the case of the eternal domination game, if the guards can choose their initial configuration and the graph is directed, the decision problem remains EXPTIME-complete. We present an algorithm that decides the problem in time 𝑂(𝑘𝑛^𝑘+2) in both games, marking a significant improvement over the previously fastest known algorithm which has time complexity 𝑂(𝑛^2𝑘+2). Our algorithm further determines the maximum number of attacks (potentially infinite) the guards can defend from each configuration.

We study the relationship between the eternal domination number of a graph and its clique covering number using both large-scale computation and analytic methods. In doing so, we answer two open questions of Klostermeyer and Mynhardt, and disprove a conjecture of Klostermeyer and MacGillivray (The Fundamental Conjecture [Eternal Domination: Criticality and Reachability, Discuss. Math. Graph Theory 37 (2017), no. 1, 63–77]). We prove that the smallest graph having its eternal domination number less than its clique covering number has ten vertices. We also demonstrate that for any integer 𝑘 ≥ 2, there exist infinitely many graphs having domination number and eternal domination number equal to 𝑘 containing dominating sets which are not eternal dominating sets. 

In addition, we show that for any integer 𝑘 ≥ 1, there exists a function 𝑓(𝑘) such that any graph with independence number at most 𝑘 has eviction number at most 𝑓(𝑘). We further show that the eviction number of a cograph can be computed in polynomial time. Finally, we study the length of both games when played on an 𝑛-vertex graph on which are located 𝑘 guards; that is, the maximum number of turns required before a winner can be decided.