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

Bachelor thesis (2022)

Authors

A.M. Primavera Electrical Engineering, Mathematics and Computer Science

Contributors

A. Bishnoi Discrete Mathematics and Optimization - EEMCS (supervisor 1)
J. Komjáthy Applied Probability - EEMCS (supervisor 1)
Carolina Urzúa-Torres Numerical Analysis - EEMCS (coach)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 Alessandra Primavera
More Info
expand_more

Published Date

16-06-2022

Language

English

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

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.