The localization game on Cartesian products
Date
2020-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
AFRIKAANSE OPSOMMING: In grafiekteorie word die opsporingspeletjie deur twee spelers gespeel: ’n Polisieman met ’n span van k polisiemanne, en ’n Skurk. Die speletjie begin deur die Skurk wat ’n node r 2 V kies, onbekend aan die Polisieman. Hierna gaan die speletjie beurtsgewys voort. Aan die begin van elke beurt kies die Polisieman k nodusse en ontvang daarna ’n afstandsvektor wat die afstand vanaf die Skurk na elk van die k nodusse aandui. As die Polisieman van die afstandsvektor kan aflei presies waar die Skurk is, dan is die Skurk opgespoor en die Polisieman wen. Andersins word die Skurk toegelaat om óf te bly by r, óf te skuif na r0 in die omgewing van r. Hierna kan die Polisieman weer k nodusse kies. Die speletjie gaan op hierdie manier voort, waar die Polisieman wen as die Skurk in ’n eindige aantal beurte opgespoor kan word. Die opsporingsgetal (G) is die kleinste heelgetal k waarvoor die Polisieman definitief kan wen, ongeag van die Skurk se strategie. In hierdie tesis val die fokus op die opsporingspeletjie wat op die Cartesiese produk van grafieke gespeel word. Bo- en ondergrense van die opsporingsgetal van twee arbitrêre grafieke word bepaal, waar die konsep van dubbeloplossingsversamelings gebruik word vir die bogrens. Wanneer die Cartesiese produk van ’n arbitrêre grafiek met ’n volledige grafiek beskou word, is die opsporingsgetal op die meeste die grootste van die twee ordes. Hierdie grens word behaal wanneer beide grafieke volledig is. Die eksakte waarde van die opsporingsgetal van die Cartesiese produk van volledige grafieke met siklusse en paaie word ook gevind. Die eksakte waarde van die opsporingsgetal van die Cartesiese produk van twee siklusse, asook van ’n siklus en ’n pad, word bepaal en ’n bogrens op die opsporingsgetal van die Cartesiese produk van ’n arbitrêre grafiek met ’n siklus word gegee. Laastens word die Cartesiese produk van sterre ondersoek. Die eksakte waarde van die opsporingsgetal van die produk van twee sterre word gevind en sodoende word daar bewys dat die verskil tussen die opsporingsgetal van G en die opsporingsgetal van die Cartesiese produk van twee kopieë van G arbitrêr groot kan wees. Daar word ook gewys dat as die opsporingsgetal van G kleiner is as die van H, dit nie impliseer dat die opsporingsgetal van G G kleiner is as die van H H nie.
AFRIKAANSE OPSOMMING: In grafiekteorie word die opsporingspeletjie deur twee spelers gespeel: ’n Polisieman met ’n span van k polisiemanne, en ’n Skurk. Die speletjie begin deur die Skurk wat ’n node r 2 V kies, onbekend aan die Polisieman. Hierna gaan die speletjie beurtsgewys voort. Aan die begin van elke beurt kies die Polisieman k nodusse en ontvang daarna ’n afstandsvektor wat die afstand vanaf die Skurk na elk van die k nodusse aandui. As die Polisieman van die afstandsvektor kan aflei presies waar die Skurk is, dan is die Skurk opgespoor en die Polisieman wen. Andersins word die Skurk toegelaat om óf te bly by r, óf te skuif na r0 in die omgewing van r. Hierna kan die Polisieman weer k nodusse kies. Die speletjie gaan op hierdie manier voort, waar die Polisieman wen as die Skurk in ’n eindige aantal beurte opgespoor kan word. Die opsporingsgetal (G) is die kleinste heelgetal k waarvoor die Polisieman definitief kan wen, ongeag van die Skurk se strategie. In hierdie tesis val die fokus op die opsporingspeletjie wat op die Cartesiese produk van grafieke gespeel word. Bo- en ondergrense van die opsporingsgetal van twee arbitrêre grafieke word bepaal, waar die konsep van dubbeloplossingsversamelings gebruik word vir die bogrens. Wanneer die Cartesiese produk van ’n arbitrêre grafiek met ’n volledige grafiek beskou word, is die opsporingsgetal op die meeste die grootste van die twee ordes. Hierdie grens word behaal wanneer beide grafieke volledig is. Die eksakte waarde van die opsporingsgetal van die Cartesiese produk van volledige grafieke met siklusse en paaie word ook gevind. Die eksakte waarde van die opsporingsgetal van die Cartesiese produk van twee siklusse, asook van ’n siklus en ’n pad, word bepaal en ’n bogrens op die opsporingsgetal van die Cartesiese produk van ’n arbitrêre grafiek met ’n siklus word gegee. Laastens word die Cartesiese produk van sterre ondersoek. Die eksakte waarde van die opsporingsgetal van die produk van twee sterre word gevind en sodoende word daar bewys dat die verskil tussen die opsporingsgetal van G en die opsporingsgetal van die Cartesiese produk van twee kopieë van G arbitrêr groot kan wees. Daar word ook gewys dat as die opsporingsgetal van G kleiner is as die van H, dit nie impliseer dat die opsporingsgetal van G G kleiner is as die van H H nie.
Description
Thesis (MSc)--Stellenbosch University, 2020.
Keywords
Localization game, Cartesian product, Computer games -- Programming, Cops and robbers -- Computer games, Set theory, UCTD