Lazy cop number and other related graph parameters / Sim Kai An

Sim , Kai An (2018) Lazy cop number and other related graph parameters / Sim Kai An. PhD thesis, Universiti Malaya.

	PDF (The Candidate's Agreement) Restricted to Repository staff only Download (177Kb)
Preview	PDF (Thesis PhD) Download (1115Kb) | Preview

Abstract

In this thesis, we focus on graph parameters in the game of Cops and Robbers and the burning number of graphs. The game of cops and robbers is a two-player game played on a finite connected undirected graph G. The first player occupies some vertices with a set of cops, and the second player occupies a vertex with a single robber. The cops move first, followed by the robber. After that, the players move alternately. On the cops’ turn, each of the cops may remain stationary or move to an adjacent vertex. On the robber’s turn, he may remain stationary or move to an adjacent vertex. A round of the game is a cop move together with the subsequent robber move. The cops win if after a finite number of rounds, one of them can move to catch the robber, that is, the cop and the robber occupy the same vertex. The robber wins if he can evade the cops indefinitely. The cop number is the main graph parameter in the game of cops and robbers. In this thesis, we investigate the cop number and lazy cop number of a graph G, the minimum order of graphs for small value of cop number and the capture time. Our results focused on a variant of the game, the lazy cops and robbers, where at most one cop moves in any round. Burning a graph is a process defined on the vertex set of a simple finite graph. Initially, at time step t = 0, all vertices are unburned. At the beginning of every time step t _ 1, an unburned vertex is chosen to burn (if such a vertex is available). Thereafter, if a vertex is burned in time step t

Actions (For repository staff only : Login required)