Hra Cops and robber na orientovaných úplných grafech

Slívová, Veronika

BACHELOR THESIS - ABSTRACT Veronika Slívová This thesis focuses on the game Cops and robber on tournaments (a graph we gain by orienting each edge of undirected complete graph). We show that tournaments containing a vertex with large outdegree have small cop number. On the other hand we prove that the number of cops we need to capture the robber on any tournament is not bounded. Then we study circulant tournaments and graphs obtained by cyclically orienting each triple of Steiner triple system. We disprove the conjecture made by Geňa Hahn that the cop number of any graph obtained by orientation Steiner triple system is bounded. We also show that the cop number of circulant tournaments cannot be bounded. Then we focus on the 2-fast cop and the 2-fast robber variant of the game. We prove that one 2-fast cop wins on any tournament. On the contrary in case that the game is played on tournament whose vertices have the same outdegree, the 2-fast robber is captured trivially or runs away indefinitely.

guest :: login Digital Repository
		Search		Submit		Help		About