Even time constraints on the watchman's walk (Q2848728)

The watchman's walk problem for a given graph \(G\) (representing a building) is stated as follows. At time \(i=0\), a number of guards are initially placed on vertices of \(G\) (representing the rooms of the building), more than one guard allowed on a vertex at a time. With each increment \(i:=i+1\) of discrete time, each guard either stays on the same vertex, or shifts onto an adjacent (neighboring) vertex. The guards are said to \(t\)-monitor \(G\) provided that for each vertex \(v\) of \(G\), and any nonnegative integers \(k\) and \(t\), some guard shows up in the close neighborhood of \(v\) at some time \(i \in \{ k, k+1, \ldots, k+t \}\). The watchman's walk problem is the problem of finding the least number of guards, denoted \(W_t(G)\), sufficient for \(t\)-monitoring of \(G\). It is easy to observe that \(W_0(G)\) is equal to the domination number \(\gamma(G)\), which is at most half of the order of \(G\).NEWLINENEWLINEThe main result of the paper under review is that \(W_t(T) \leq \lfloor \frac {2n+t-2}{t+3} \rfloor\) for any even integer \(t > 0\) and any tree \(T\) on \(n \geq 3\) vertices. This proves in the affirmative a recent conjecture due to \textit{D. Dyer} and \textit{R. Milley} [Australas. J. Comb. 53, 97--108 (2012; Zbl 1256.05167)].