Masters Degrees (Applied Mathematics)

Permanent URI for this collection

https://scholar.sun.ac.za/handle/10019.1/96344

Browse

Browsing Masters Degrees (Applied Mathematics) by Author "Boshoff, Jeandre"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    The localization game on Cartesian products
    (Stellenbosch : Stellenbosch University, 2020-12) Boshoff, Jeandre; Roux, Riana; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Division Applied Mathematics.
    ENGLISH ABSTRACT: The localization game is played by two players: a Cop with a team of k cops, and a Robber. The game is initialised by the Robber choosing a vertex r 2 V , unknown to the Cop. Thereafter, the game proceeds turn based. At the start of each turn, the Cop probes k vertices and in return receives a distance vector that indicates the distance from the Robber to each of the k vertices. If the Cop can determine the exact location of r from the vector, the Robber is located and the Cop wins. Otherwise, the Robber is allowed to either stay at r, or move to r0 in the neighbourhood of r. The Cop then again probes k vertices. The game continues in this fashion, where the Cop wins if the Robber can be located in a finite number of turns. The localization number (G), is defined as the least positive integer k for which the Cop has a winning strategy irrespective of the moves of the Robber. In this thesis, the focus falls on the localization game played on Cartesian products. Upper and lower bounds on the localization number of two arbitrary graphs are established, where the concept of doubly resolving sets are used for the upper bound. When the Cartesian product of an arbitrary graph with a complete graph is considered, the localization number is at most the largest of the orders of the graphs. This bound is achieved when both graphs are complete graphs. The exact values of the localization number of the Cartesian product of complete graphs with cycles and paths are also established. The exact values of the localization number of the Cartesian product of two cycles as well as a cycle with a path are determined and an upper bound on the localization number of the Cartesian product of an arbitrary graph and a cycle is presented. Lastly the Cartesian products of stars are investigated. The exact value of the localization number of the product of two stars is established, showing that the difference between the localization number of G and the localization number of the Cartesian product of two copies of G can be arbitrarily large. It is also illustrated that if the localization number of G is less than that of H, it does not imply that the localization number of G G is less than that of H H.