Zombies and survivors on graph classes
| dc.contributor.author | Liu, Fengyi | |
| dc.contributor.examiningcommittee | Gunderson, Karen (Mathematics) | |
| dc.contributor.examiningcommittee | Durocher, Stephane (Computer Science) | |
| dc.contributor.supervisor | Miller, Avery | |
| dc.date.accessioned | 2024-03-20T14:36:12Z | |
| dc.date.available | 2024-03-20T14:36:12Z | |
| dc.date.issued | 2024-03-14 | |
| dc.date.submitted | 2024-03-15T01:39:29Z | en_US |
| dc.degree.discipline | Computer Science | en_US |
| dc.degree.level | Master of Science (M.Sc.) | |
| dc.description.abstract | Zombies and Survivors is a two-player graph game introduced by Fitzpatrick et al. as a variant of Cops and Robbers. These games can be used to model situations involving pursuit-evasion or search-and-rescue. Two players take turns to move their pieces in a given graph, with the condition that the zombie pieces must move toward the survivor along a shortest path during the zombie player’s turn. The minimum number of zombies that is sufficient to catch the survivor is called the graph's zombie number. First, we give a construction of graphs with zombie number equal to any given k, and extend the result to a construction of graphs that simultaneously have zombie number equal to any given k and cop number equal to any given m. Then, we investigate specific graph classes. We determine the exact zombie number of the Cartesian product of a cycle and a path, and show that this quantity depends on the parity of the cycle. Upper bounds on the zombie number for strong products, Cartesian products and lexicographic products are given. We also show that the throttling numbers of Cartesian products and strong products of two paths are asymptotic to a sublinear polynomial in the length of the path. Finally, the class of graphs formed by a set of cycles with one common center vertex is investigated, and we give a characterization of such graphs that have zombie number 1 or 2. | |
| dc.description.note | May 2024 | |
| dc.identifier.uri | http://hdl.handle.net/1993/38062 | |
| dc.language.iso | eng | |
| dc.rights | open access | en_US |
| dc.subject | pursuit-evasion on graphs | |
| dc.subject | cops and robbers | |
| dc.subject | zombies and survivors | |
| dc.title | Zombies and survivors on graph classes | |
| dc.type | master thesis | en_US |
| local.subject.manitoba | no |