Deduction with k k moves
Andrea C. Burgess, Nancy E. Clarke, Shannon L. Fitzpatrick, Melissa A. Huggan · 2025
Read Deduction with k k moves by Andrea C. Burgess, Nancy E. Clarke, Shannon L. Fitzpatrick, Melissa A. Huggan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-24959.txt.
Introduction
Andrea C Burgess, Nancy E Clarke, Shannon L Fitzpatrick, and Melissa A Huggan stretch a hunt game on graphs where each hunter moves once at most. In the base game, hunters seek a hid robber on a graph, but hunters on far points can not talk to plan. Their new form lets each hunter make up to a set count of moves.
They weigh the new hunt count for a few graph kinds: paths, loops, full graphs, and two part full graphs. Linked forms built as grid and strong blends of paths are also worked out. The count tells how many hunters a graph needs when moves are capped. More moves per hunter change the count in ways that shift by graph type.
Catalog record
| CREATOR | Andrea C. Burgess, Nancy E. Clarke, Shannon L. Fitzpatrick, Melissa A. Huggan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-24959
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Deduction with k k moves Andrea C. Burgess, Nancy E. Clarke, Shannon L. Fitzpatrick, Melissa A. Huggan Abstract The deduction game may be thought of as a variant on the classical game of cops and robber in which the cops (searchers) aim to capture an invisible robber (evader); each cop is allowed to move at most once, and cops situated on different vertices cannot communicate to co-ordinate their strategy. In this paper, we extend the deduction game to allow each searcher to make k k moves, where k k is a fixed positive integer. We consider the value of the k k -move deduction number on several classes of graphs including paths, cycles, complete graphs, complete bipartite graphs, and Cartesian and strong products of paths. Keywords: Graph searching, deduction game, cops and robber MSC2020: 05C57 1 Introduction The deduction game , which was introduced in [ 3 , 7 ] , may be thought of as a variant on the classical game of cops and robber. Cops and robber, first considered in [ 8 , 9 ] , is a two-player game on a graph, with one player controlling a set of cops and the other controlling a single robber. The cops and robber are positioned on vertices, and play proceeds in alternating turns; on a turn, players may move their token(s) to an adjacent vertex or pass. The aim of the cops is to capture the robber by occupying the robber’s vertex, while the robber attempts to avoid capture indefinitely. While many variants of cops and robber have been proposed (see, for instance, [ 2 , Chapter 8] ), deduction arose from variants which restrict the cops, particularly zero-visibility cops and robber (see [ 5 , 6 , 10 , 11 ] ), in which the cops cannot see the robber’s location until the moment of capture, and time-constrained variants (see [ 1 ] ), in which the cops must achieve capture within a fixed number of turns in order to win. Deduction adds to these the restriction that cops situated on different vertices cannot communicate to co-ordinate their strategy; thus cops’ movements depend on local conditions regarding the vertices in their immediate neighbourhood. In the deduction game as initially defined in [ 3 , 7 ] , cops are termed searchers . Each searcher is permitted to move at most once. In this paper, we extend the game to allow searchers k moves, where k is a fixed positive integer. We view deduction as a multi-stage process. In the initial set-up, searchers are placed on vertices of a graph. The initial placement of the searchers is called a layout . Note that in a layout, searchers need not be situated on distinct vertices. Each searcher is initially considered mobile . A vertex occupied by a searcher is thereafter protected , while vertices which have not been visited by searchers are unprotected . At each stage of the game, searchers on a vertex v move to unprotected neighbours of v if the number of mobile searchers on v is at least the number of its unprotected neighbours. If the number of mobile searchers on v exceeds the number of unprotected neighbours, the excess searchers may move to any of the unprotected neighbours. Any searchers who have moved k times become immobile and cannot move again. This process repeats until either all vertices are protected or all searchers are immobile. Note that k restricts the number of times a searcher moves and not the number of stages it takes for this to happen. That is, while a searcher becomes immobile after having moved k times, this need not occur in the k^{\mathrm{th}} stage of the game. As well, two searchers may become immobile at different stages. The searchers win if at the end of the game, all the vertices are protected; in this case we call the initial layout successful . The k -move deduction number of the graph G , denoted d_{k}(G) , is the minimum number of searchers for which there exists a successful layout on G . If k=1 , then we omit it from the notation and simply write d(G) . The k -move capture time of a graph G is the minimum number of stages that it takes for all vertices to become protected over all successful layouts with d_{k}(G) searchers. If the value of k is clear, we will simply refer to capture time . Note that if the k -move capture time is equal to 1 , then d_{k}(G)=d(G) . For this reason, we are primarily interested in cases where the capture time is greater than 1 . As an illustration of the deduction process, consider the graph G illustrated below. t v u w x y z Using [ 3 , Theorem 5.2] , it can be seen that d(G)=5 ; a successful layout in 1 -move deduction is given by placing searchers on vertices t , v , w , y and z . By contrast, if searchers may move twice, three searchers can protect all vertices. Placing searchers on vertices t , y and w , in the first stage searchers move from t and y to u and x , respectively, and in the second stage the same searchers move to v and z . It is easy to see that no successful layout is possible with two searchers, so d_{2}(G)=3 . Similarly we obtain d_{3}(G)=3 . However, moving to 4 -move deduction there is a successful layout with two searchers so that d_{4}(G)=2 . To see this, place searchers on t and v . In the first stage, both searchers move to u . In the second stage, one of these searchers must move to w ; the second may also do so. Subsequently, both may move to x , and in the final stage one searcher moves to y and the other to z , clearing the graph. The paper [ 3 ] introduces the 1 -move deduction game, gives various bounds on d(G) and considers the value of the 1 -move deduction number on several classes of graphs including Cartesian products and trees. The paper [ 4 ] explores connections between deduction and constrained versions of other graph processes, namely zero forcing and fast-mixed search, and gives a structural characterization of graphs with given deduction number and additional lower bounds on d(G) . Nevertheless, determining the value of d(G) is NP-complete [ 4 ] . The following theorem summarizes the bounds on the 1 -move deduction number from [ 3 , 4 ] . Theorem 1.1 ( [ 3 , 4 ] ) . In any connected graph G of order n\geq 3 which contains \ell vertices of degree 1 , \max\left\{\left\lceil\frac{n}{2}\right\rceil,\ell,\delta(G),\alpha(G),\omega(G)-1\right\}\leq d(G)\leq n-1, where \alpha(G) is the independence number of G and \omega(G) is the clique number of G . In this paper, we consider deduction with k\geq 2 moves. In Section 2, we verify that given any successful layout, with the seachers and evaders moving in turn as described in the previous section, the searchers will always capture the evader. In Section 3, we find the k -move deduction number for common families of