Localization on locally finite trees

Introduction

#

I’ll use the same notation as this paper by Bonato, Lehner, Marbach, and Nir as closely as I can. That means that for any tree \(T\), the localization number of \(T\) is expressed with \(\zeta(T)\). There are also a few precisely defined trees. There’s \(\hat{T}\), which looks like this:

As well as \(T_1^\infty\), which looks like this:

It is already known that any tree containing \(\hat{T}\) or \(T_1^\infty\) has localization number 2. In fact, every finite tree with localization number 2 contains an instance of \(\hat{T}\). However, it is not clear if every locally finite tree with localization number 2 contains a tree in \({\hat{T},T_1^\infty}\). The exact question posed is:

Or, rephrased

Finding one simple tree that is not a hideout

#

It’s nice that the scope of the question is limited with that second question. I’ll build larger and larger trees that do not contain \(\hat{T}\) or \(T_1^\infty\), and see when we get a localization number above 1.

Let \(T\) be a 2-ended tree that does not contain \(T_1^\infty\) or \(\hat{T}\). Because \(T\) does not contain \(T_1^\infty\), it must have a double ray with at least one vertex of degree 2. Label that vertex with degree 2 \((0,0)\), and label the other points along that double ray with \((n,0)\). For any vertex \(V\) on \(T\) that is not on the double ray, label \(V\) with \(n,m\) if \(V\) is closer to \((n,0)\) than any other point on the double ray, and \(V\) is a distance of \(m\) from \((n,0)\).

For any \(n\neq0\), let \(N\) be a finite subtree rooted at \((n,0)\). If the cop ever knows that the robber is on \(N\), then the robber can be found by the same method described in this paper by Seager. That gives me the initial impression that a 2-ended graph with length 2 paths on each vertex \((n,0)\) with \(n\neq0\), as shown.

As defined, \(T\) has a localization number 1.

proof:
For this proof, I’ll first show that the robber can be restricted to the vertices \({(n,0),(n+1,1),(n+2,2)}\) for positive \(n\). Then, I’ll show that this can be pushed to \({(0,0),(1,1),(2,2)}\). Finally, from there, the cop may locate the robber.

First, the cop may probe at \((0,0)\) and receive a distance from the robber of \(d\). The robber set at that point is:

$$ \left\{(-d,0),(-d+1,1),(-d+2,2),(d-2,2),(d-1,1),(d,0)\right\} $$

Next, the cop may probe at \((-d-1,0)\). The possible distances from that point to points in the extended robber set is:

If the second probe gives a distance of \(0\) or \(1\), the robber is found instantly. If the second probe gives a distance of \(2\) or \(3\), then the robber has been restricted to vertices of the form \({(-n,0),(-n-1,1),(n-2,2)}\), which is identical to \({(n,0),(n+1,1),(n+2,2)}\) up to sign. If the second probe gives a distance above 3, then a third probe is required.

If a third probe is required, we have so far restricted the robber to one of three sets, whose union is:

$$ \left\{(d-2,1), (d-1,0),(d-2,2), (d-1,1),(d,0),(d-1,2), (d,1),(d+1,0)\right\} $$

Therefore, let the cop put the third probe at \((d+2,0)\), giving the following robber sets:

Regardless of what distance is found in the third probe, the robber is restricted to a set of vertices \(\{(n,0),(n+1,1),(n+2,2)\}\). Next, the cop may push the robber to \(\{(n-1,0),(n,1),(n+1,2)\}\) using the following sequence of probes:

Once the cop has pushed the robber to \({(0,0),(1,1),(2,2)}\), the robber can be found with the following probing strategy:

Unfortunately, this proof doesn’t work if the cop never probes vertices off the double ray. This means that the translation of this proof to versions of \(T\) with different subtrees coming off the double ray require closer inspection. So let’s take this same proof concept and expand it to larger trees.

A larger tree that is not a hideout

#

As promised, I’ll extend the previous theorem to a larger tree. Let \(T\) be a 2-ended tree with vertices uniquely labelled with \((n,m)\), with \(n\in\mathbb{Z}/0\) and \(m\in\mathbb{Z}\cap[0,h]\) where \(h\) is any natural number, as well as a vertex labelled \((0,0)\). The tree \(T\) will also contain edges between the vertices \((n,0)\) and \((n+1,0)\) for any \(n\), and an edge between vertices \((n,m)\) and \((n,m+1)\) for any \(n,m\). For convenience, this is illustrated here:

In other words, each vertex on the double ray has an arbitrarily long path coming off it. This graph will be shown to have localization number 1 using the same method used previously.

proof:

The cop may probe first at \((0,0)\), and receive a distance of \(d\). If they then probe at \((-d,0)\), it will be clear if the robber is located at a vertex with a positive or negative \(x\)-coordinate. Without loss of generality, assume the robber is determined to lie to the right of \((0,0)\).

The cop will then probe once to the left of the robber, then once to the right. The cop may probe at \((0,0)\) and receive a distance of \(d_1\). The robber set at that point consists of all vertices \((d_1-i,i)\) where \(i\) is a natural number less than \(h\) and \(d_1\). The extended robber set consists of the vertices \((d_1-i+\psi,i)\), where \(\psi\in[-1,0,1]\).

Next the cop may probe to the right of the robber, specifically at \((d_1+1,0)\), and receive distance \(d_2\). If \(d_2\) is 0 or odd, the robber is instantly found, so assume \(d_2\) is even. If \(d_2=2\), then the robber is restricted to \(\{(d_1-1,0),(d_1,1)\}\), satisfying the lemma statement. So assume now that \(d_2\geq4\) and that the robber is restricted to some set of vertices \({(n,m),(n+1,m+1)}\). I’ll illustrate the options for this as well.

As mentioned, the robber is now restricted to a set of 2 vertices \({(n,m),(n+1,m+1)}\). If \(m>1\), then that set is raised slightly off the double-ray, giving an extended robber set of \({(n,m+\psi),(n+1,m+1+\psi)}\) for all values of \(\psi\in[-1,0,1]\). The cop will now probe at \((n,1)\).

If \(m>1\), then probing at \((n,1)\) instantly reveals the location of the robber, as shown in the following table:

If \(m=1\), then the robber is restricted to a pair of vertices labeled \((n,1)\) and \((n+1,2)\). The cop can either locate the robber or shift the robber to vertices labeled \((n-1,0)\) and \((n,1)\) with the following two moves: