Search Cops and robber as keywords on MyScienceWork's publications...

This dissertation contains various combinatorial results about games graphs and finite Abelian groups A linear configuration is said to be common in an Abelian group G if every 2-colouring of G yields at least as many monochromatic instances of the configuration as a randomly chosen colouring In Chapter 2 we show that every configuration containing a 4-term arithmetic progression is uncommon in mathbb F p n for primes p geq 5 and large n and in mathbb Z p for large primes p We call a graph H strongly common if for every colouring phi of K n with two colours the number of monochromatic copies of H is at least the number of monochromatic copies of H in a random colouring of K n with the same density of colour classes as phi In Chapter 3 we prove that if a graph has odd girth but is not a cycle then it is not strongly common We also discuss the commonness property for hypergraphs A set A subset mathbb F p n is sum-free if it contains no elements x y and z such that x y z If p equiv 2 mod 3 the maximal size of a sum-free in mathbb F p n is known to be p n p n-1 3 In Chapter 4 we show that if a sum-free subset of mathbb F p n is larger than p n 3-p n-1 6 p n-2 then it is contained in p 1 3 cosets of a subspace of codimension 1 For p 5 we prove the stronger bound 1 2 cdot 5 n-1 We say that a family mathcal C of graphs on n vertices is a linear graph code if the symmetric difference of the edge sets of any two graphs in mathcal C is also the edge set of a graph in mathcal C In Chapter 5 we investigate the maximal size of a linear graph code that does not contain a copy of a fixed graph H In particular we show that for almost all graphs H with an even number of edges there exists varepsilon H 0 such that the size of a linear graph code without a copy of H is at most 2 binom n 2 n varepsilon H The game cops and robbers is played on a graph G by two players where one of them controls k cop pieces and the other controls a single robber piece The players take turns to move their pieces along the edges between vertices of G and the cop player attempts to have his pieces catch the robber piece In Chapter 6 we present a new algorithm that determines for any G and k whether the cops can catch the robbers with optimal play We will also prove sufficient conditions for a cop-win in terms of the independence and domination numbers of G In the domination game two players called Dominator and Staller select vertices in a graph G alternately A vertex is said to be dominated if it has been selected or is adjacent to a selected vertex Each selected vertex must dominate a new vertex and the game ends once every vertex in G is dominated Dominator aims to keep the game as short as possible while Staller tries to achieve the opposite In Chapter 7 we prove that for any graph G on n vertices Dominator has a strategy to end the game in at most 3n 5 moves In Chapter 8 we show that if G has n vertices and minimum degree 2 then Dominator has a strategy to end the game in at most lceil 10n 17 rceil moves Finally in Chapter 9 we show that if we replace the notion of domination by total domination then Dominator has a strategy to end the game in 3n 4 moves Trinity College External Researcher Studentship

Games, Graphs, and Groups

Edge-critical cops and robber in planar graphs

Publication search with Cops and robber as keyword

Games, Graphs, and Groups

Edge-critical cops and robber in planar graphs

Publication search
with Cops and robber as keyword