On the domination number and cop number of Erdős–Rényi random graphs

On the domination number and cop number of Erdős–Rényi random graphs

Primavera, Alessandra (TU Delft Electrical Engineering, Mathematics and Computer Science)

Bishnoi, A. (mentor)
Komjáthy, J. (mentor)
Urzúa-Torres, Carolina (graduation committee)

Delft University of Technology

Applied Mathematics

2022-06-16

We consider the game cops and robbers, which is a pursuit-evasion game played on a graph G. The cops and the robber take turns moving across the vertices of G, where the goal for the cops is to eventually catch the robber. Specifically, we study the cop number of G, i.e. the minimum number of cops that is needed to catch the robber on G. We investigate the relation between the cop number of the Erdős-Rényi (ER) random graph G(n, p_n) and compare it to another graph parameter, the domination number. Our goal is to collect results from previous research and create an overview. Throughout this thesis, we provide some examples of graphs for which the cop number is equal to the domination number. Furthermore, we provide proofs for some results on the domination number of the ER random graph. The main takeaway is that the cop number is asymptotic to the domination number for particular values of p_n.

Random Graph
Cops and robbers
Domination number
Cop number
Graph theory
Graph games

http://resolver.tudelft.nl/uuid:8df60791-fadf-4639-9438-a6379696e64b

Student theses

bachelor thesis

© 2022 Alessandra Primavera