- Email: [email protected]

)

–

Contents lists available at ScienceDirect

Discrete Applied Mathematics journal homepage: www.elsevier.com/locate/dam

The fast search number of a Cartesian product of graphs Yuan Xue, Boting Yang ∗ Department of Computer Science, University of Regina, Canada

article

info

Article history: Received 11 April 2016 Received in revised form 30 October 2016 Accepted 8 March 2017 Available online xxxx Keywords: Graph searching Fast searching Cops and robber game

abstract Given a graph that contains an invisible fugitive, the fast searching problem is to find the fast search number, i.e., the minimum number of searchers to capture the fugitive in the fast search model. In this paper, we give a new lower bound on the fast search number. Using the new lower bound, we prove an explicit formula for the fast search number of the Cartesian product of an Eulerian graph and a path. We also give formulas for the fast search number of variants of the Cartesian product. We present an upper bound on the fast search number of hypercubes, and extend the results to a broader class of graphs including toroidal grids. © 2017 Elsevier B.V. All rights reserved.

1. Introduction Motivated by applied problems in the real world and theoretical issues in computer science and mathematics, graph searching has become a hot topic. It has many models, such as edge searching, node searching, mixed searching, fast searching, etc. These models are basically defined by the class of graphs, the actions of searchers and fugitives, visibility of fugitives, and conditions of captures [1,2,4,5,9,10]. Parsons [14] first introduced the graph search problem in which both searchers and fugitive move continuously along edges of a graph. Megiddo et al. [13] studied the discrete version of Parsons’ model, called edge search problem. In the edge search model, there are three actions for searchers: placing a searcher on a vertex, removing a searcher from a vertex and sliding a searcher along an edge from one endpoint to the other. An edge is cleared by a sliding action. Kirousis and Papadimitriou [11] introduced the node search problem, in which there are two actions for searchers: placing and removing. An edge becomes cleared if both endpoints are occupied by searchers. Bienstock and Seymour [3] introduced the mixed search problem, which is a combination of the edge searching and node searching. In the mixed search problem, searchers have the same actions as those in the edge search model, and an edge is cleared if both of its endpoints are occupied by searchers or cleared by a sliding action. Dyer et al. [8] introduced the fast search problem. They proposed a linear time algorithm for computing the fast search number of trees. In the fast search model, there are two actions for searchers: placing and sliding. An edge is cleared by a sliding action and every edge is traversed exactly once. Details of this model will be given in Section 2. Stanley and Yang [15] gave a linear time algorithm for computing the fast search number of Halin graphs and their extensions. They also presented a quadratic time algorithm for computing the fast search number of cubic graphs, while the problem of finding the node search number of cubic graphs is NP-complete [12]. Yang [17] proved that the problem of finding the fast search number of a graph is NP-complete; and it remains NP-complete for Eulerian graphs. He also proved that the problem of determining whether the fast search number of G is a half of the number of odd vertices in G is NP-complete; and it remains NP-complete for planar graphs with maximum degree 4. Dereniowski et al. [7] characterized graphs for which 2 or 3 searchers are sufficient in the

∗

Corresponding author. E-mail addresses: [email protected] (Y. Xue), [email protected] (B. Yang).

http://dx.doi.org/10.1016/j.dam.2017.03.003 0166-218X/© 2017 Elsevier B.V. All rights reserved.

2

Y. Xue, B. Yang / Discrete Applied Mathematics (

)

–

fast search model. They proved that the fast searching problem is NP-hard for multigraphs and for graphs. Very recently, Xue et al. [16] provided lower bounds and upper bounds on the fast search number of complete k-partite graphs. They solved the open problem of determining the fast search number of complete bipartite graphs. They also presented upper and lower bounds on the fast search number of complete split graphs. This paper is organized as follows. In Section 2, we give some definitions and notation. In Section 3, we first consider the trail covering problem, and show its relations to the fast searching problem. We then give a new lower bound on the fast search number. Using the new lower bound, we give an explicit formula for the fast search number of the Cartesian product of an Eulerian graph and a path. In Section 4, we investigate the fast search number of hypercubes. We prove an upper bound and a lower bound respectively on the fast search number of hypercubes. Section 5 concludes the paper with some open problems. 2. Preliminaries Throughout this paper, we only consider finite undirected graphs with no loops or multiple edges. Let G = (V , E ) be a graph with vertex set V and edge set E. We also use V (G) and E (G) to denote the vertex set and edge set of G respectively. We use uv to denote an edge with endpoints u and v . For a vertex v ∈ V , the degree of v is the number of edges incident on v , denoted degG (v). A leaf is a vertex that has degree one. A vertex is odd when its degree is odd. An odd graph is a graph with vertex degrees all odd. Similarly, a vertex is even when its degree is even; and an even graph is a graph with vertex degrees all even. Define Vodd (G) = {v ∈ V : v is odd}. For a subset V ′ ⊆ V , we use G[V ′ ] to denote the subgraph induced by V ′ , which consists of all vertices of V ′ and all the edges of G between vertices in V ′ . We use G − V ′ to denote the induced subgraph G[V \ V ′ ]. For a subset E ′ ⊆ E, we use G − E ′ to denote the subgraph (V , E \ E ′ ). Let G1 = (V1 , E1 ) and G2 = (V2 , E2 ) be two subgraphs of G (the intersection of V1 and V2 may not be empty). The union of two graphs G1 and G2 is the graph G1 ∪ G2 = (V1 ∪ V2 , E1 ∪ E2 ). We use G1 + V2 to denote the induced subgraph G[V1 ∪ V2 ] and we also use G1 + E2 to denote the subgraph (V1 ∪ V (E2 ), E1 ∪ E2 ), where V (E2 ) is the vertex set of all edges in E2 . Given two graphs H1 and H2 , the Cartesian product of H1 and H2 , denoted by H1 H2 , is the graph whose vertex set is the Cartesian product V (H1 ) × V (H2 ) and in which two vertices (u, v), (u′ , v ′ ) ∈ V (H1 ) × V (H2 ) are adjacent in H1 H2 if and only if u = u′ and v is adjacent to v ′ in H2 , or v = v ′ and u is adjacent to u′ in H1 . A walk is a sequence v0 , e1 , v1 , . . . , ek , vk of vertices and edges such that each edge ei , 1 ≤ i ≤ k, has endpoints vi−1 and vi . A path is a walk in which every vertex appears once, except that its first vertex might be the same as its last. We use v0 v1 . . . vk to denote a path with ends v0 and vk . A cycle is a path in which its first vertex is the same as its last vertex. We use v0 v1 . . . vk v0 to denote a cycle with k + 1 vertices. We will also use Pn to denote a path with n vertices and Cn to denote a cycle with n vertices, respectively. A trail is a walk that does not contain the same edge twice. For a connected subgraph G′ with at least one edge, an Eulerian trail of G′ is a trail that traverses every edge of G′ exactly once. A circuit is a trail that begins and ends on the same vertex. An Eulerian circuit of G′ is an Eulerian trail of G′ that begins and ends on the same vertex. A graph is called Eulerian if it contains an Eulerian circuit that traverses all its edges. We will use Bm to denote an Eulerian graph with m vertices. Note that we only consider finite graphs with no loops or multiple edges. So an Eulerian circuit or Eulerian subgraph contains at least three edges throughout this paper. A trail cover of a graph G is a family of edge-disjoint trails in G that contain every edge of G. The minimum number of such trails is called the trail cover number of G and is denoted by τ (G). In the fast search model introduced by Dyer et al. [8], an invisible fugitive hides either on a vertex or along an edge, and he can move at a high speed at any moment from a vertex to another vertex along a path that contains no searchers. We call an edge uv contaminated if uv may contain the fugitive. An edge uv that does not contain the fugitive is called cleared. One of the two actions can happen in each step of the fast search model:

• placing a searcher on a vertex; or • sliding a searcher along a contaminated edge from one endpoint to the other. Note that the above sliding action is slightly different from the one used in the edge search model, in which a searcher is allowed to slide along a cleared edge. An edge uv can be cleared in one of the following two ways:

◦ if u is occupied by at least two searchers, one of them slides along uv from u to v ; or ◦ if u is occupied by only one searcher and uv is the only contaminated edge incident on u, the searcher on u slides to v along uv . In the fast search problem, we always suppose that all edges are contaminated initially and each edge will be cleared by a sliding action, that is, the fugitive is captured at the moment when the last contaminated edge is cleared; we also suppose that for each contaminated edge, after it is cleared, it will not get recontaminated in the remaining steps. Since searchers are allowed to slide only on contaminated edges, every edge will be traversed exactly once when all edges are cleared. A fast search strategy of a graph is a sequence of placing and sliding actions that clear all edges of the graph. Since searchers cannot be removed from the graph or ‘‘jump’’ from a vertex to another vertex, we can assume, without loss of generality, that all placing actions in a fast search strategy take place before all sliding actions. The fast search number of a graph G, denoted by fs(G), is the smallest number of searchers needed to capture the fugitive in G. We say that a fast search strategy of G is

Y. Xue, B. Yang / Discrete Applied Mathematics (

)

–

3

Fig. 1. fs(G1 ) = 4, fs(G2 ) = 2, fs(G3 ) = 7 and fs(G4 ) = 3. Table 1 A comparison of the search numbers of the graphs in Fig. 1.

Edge search number Node search number Mixed search number Fast search number Fast-mixed search number

G1

G2

G3

G4

2 2 2 4 7

2 3 2 2 6

3 3 2 7 2

3 3 3 3 7

optimal if we can use this strategy to capture the fugitive and the number of searchers required by this strategy is fs(G). As examples, some graphs and their fast search numbers are given in Fig. 1. The fast search model is a variant of the edge search model [13]. Specifically, if searchers cannot be removed from the graph and every edge can be traversed exactly once, then the edge search model is transformed to the fast search model. A relationship between the fast search model and the node search model [11] is described in Theorem 4.6 from [17]. Since the mixed search model [3] is a combination of the edge search model and the node search model, and the fast-mixed search model [18] is a combination of the mixed search model and the fast search model, it is easy to see that the fast search model is also related to these two models. Although the fast search model is related to the above graph search models, it can reflect different graph structures. To show the difference, let us consider Fig. 1 again. Table 1 gives a comparison of the search numbers of the four graphs in Fig. 1. 3. Lower bounds and Cartesian products In this section, we first give lower bounds on the fast search number. We then apply the lower bounds to proving a formula for the fast search number of the Cartesian product of an Eulerian graph and a path. 3.1. Lower bounds We first consider two lower bounds on fs(G). Lemma 1 ([8]). For any connected graph G, fs(G) ≥

1 2

|Vodd (G)|.

Lemma 2 ([15]). For any connected graph G with no leaves, fs(G) ≥

1 2

|Vodd (G)| + 2.

We now establish relations between a graph and its subgraph under some constraints. Lemma 3. Given a graph G, let W be a subset of V (G). If G′ is a graph obtained from G by adding a pendant edge to each vertex in W , then fs(G) ≤ fs(G′ ). Proof. For an optimal fast search strategy S of G′ , we can modify the strategy in the following way so that the new strategy S ′ can clear G. In S , if a searcher is placed on a vertex v ∈ V (G′ ) \ V (G), which is a leaf neighbor of a vertex v ′ ∈ W , then let the searcher be placed on v ′ and remove the sliding action from v to v ′ ; if a searcher stays on a vertex v ∈ V (G′ ) \ V (G) at the end of searching, which is a leaf neighbor of a vertex v ′ ∈ W , then let the searcher stay on v ′ and remove the sliding action from v ′ to v . Clearly, the modified strategy S ′ can clear all edges of G. Therefore, fs(G) ≤ fs(G′ ). Lemma 4. Given a graph G, let W be a subset of Vodd (G). If H is a graph obtained from G by adding a pendant edge to every vertex in W , then fs(G) = fs(H ). Proof. Let S be an optimal fast search strategy of G. From [8] we know every vertex in Vodd (G) should contain at least one searcher at the beginning or at the end of the search process. For each searcher used in S , we do the following modification to obtain a fast search strategy for G′ : if the searcher is placed on a vertex v ∈ W in S , then we place him on its leaf neighbor v ′ ∈ V (H ) \ V (G), and let him slide from v ′ to v ; if the searcher stays on a vertex v ∈ W in the end of S , then we let the searcher take an extra sliding action from v to its leaf neighbor v ′ ∈ V (H ) \ V (G) along the edge vv ′ .

4

Y. Xue, B. Yang / Discrete Applied Mathematics (

)

–

It is easy to see that the modified search strategy can clear all edges of H. So fs(G) ≥ fs(H ). It follows from Lemma 3 that fs(G) ≤ fs(H ). Therefore fs(G) = fs(H ). The following lemma shows a relation between the trail cover number and the number of odd vertices. Lemma 5. If G is a graph that contains at least one edge, then

τ (G) = µ(G) + |Vodd (G)|/2, where µ(G) is the number of connected components in G that are Eulerian. Proof. If Vodd (G) = ∅, then each connected component of G, which contains at least one edge, is Eulerian. Thus τ (G) = µ(G). Suppose that Vodd (G) ̸= ∅. Let G′ be a graph obtained from G by deleting all connected components of G that are Eulerian. Note that the number of odd vertices in a graph is even. Since each odd vertex must be an end vertex of a trail in any trail cover of G′ , we know that τ (G′ ) ≥ |Vodd (G′ )|/2. We now show that there is a trail cover of G′ whose cardinality is at most |Vodd (G′ )|/2. Let a and b be any two odd vertices in a connected component of G′ and let P be a trail between them. After deleting all edges of P from G′ , the remaining graph G′ − E (P ) has two fewer odd vertices than G′ , that is, Vodd (G′ − E (P )) = Vodd (G′ ) \ {a, b}. We repeat this process until the remaining graph H contains no odd vertices. Thus H is a graph with vertex degrees all even. Let S be the set of all trails deleted from G′ and H ′ be the graph obtained from H by deleting all isolated vertices from H. Each connected component H ′′ in H ′ must have a vertex that is contained in some trail of S, say P. Since H ′′ is Eulerian, we can merge H ′′ and P into a new trail P ′ , and replace P of S by P ′ . In this way, every edge of G′ is contained in a trail of S. Thus S is a trail cover of G′ whose cardinality is |Vodd (G′ )|/2. Hence τ (G′ ) ≤ |Vodd (G′ )|/2. Therefore, we have

τ (G) = µ(G) + τ (G′ ) = µ(G) + |Vodd (G′ )|/2 = µ(G) + |Vodd (G)|/2. Theorem 6. Let G be a connected graph and H be a graph obtained from G by adding two pendant edges on each vertex of G. (i) If there is an odd vertex in G, then fs(H ) = τ (H ) = |V (G)| + τ (G). (ii) If there is no odd vertex in G, then fs(H ) = τ (H ) = |V (G)|. Proof. (i) From Lemma 5 and the fact that |Vodd (H )| = |Vodd (G)| + 2|V (G)|, we have

τ (H ) =

1 2

|Vodd (H )| =

1 2

|Vodd (G)| + |V (G)| = |V (G)| + τ (G).

We now show that fs(H ) = |V (G)| + τ (G). From the definition of fast searching, we know that a fast search strategy of G corresponds to a trail covering of G. Thus, fs(H ) ≥ τ (H ) = |V (G)| + τ (G). On the other hand, for a vertex v ∈ V (G), let v ′ and v ′′ be two leaf neighbors of v . If we place a searcher on each v ′ in H and slide them to each vertex v in G, then we can use τ (G) additional searchers to clear all edges of G. Finally, we slide a searcher on each vertex v in G to v ′′ in H. In this way we clear H using |V (G)| + τ (G) searchers. So fs(H ) ≤ |V (G)| + τ (G), and hence, fs(H ) = |V (G)| + τ (G). (ii) Since G is connected and has no odd vertex, we know that τ (H ) = 21 |Vodd (H )| = |V (G)|. It follows from Lemma 1 that

fs(H ) ≥ 21 |Vodd (H )| = |V (G)|. If G contains only one vertex, then the statement is trivial. Suppose that G contains at least one edge. Since G is Eulerian, it must contain at least one cycle. Then we can use a fast search strategy, which is similar to the one described in the proof of Lemma 12, to clear the graph H using |V (G)| searchers. Thus fs(H ) ≤ |V (G)|, and therefore, fs(H ) = |V (G)|. We can extend the fast search strategy in the proof of Theorem 6(i) to clear the Cartesian product of G and a path. So we have the following corollary. Corollary 7. If G is a connected graph and P is a path, then fs(GP ) ≤ |V (G)|+τ (G)|V (P )|, where equality holds if G is Eulerian and P contains only one edge.

Proof. Note that GP can be decomposed into |V (P )| vertex-disjoint copies of G, which are denoted as G1 , . . . , G|V (P )| respectively. We first place a searcher on each vertex of G1 ; we can use τ (G) additional searchers to clear every edge of G1 . Then we slide a searcher from each vertex in G1 to its corresponding vertex in G2 along the edge between them. Similarly, we can use τ (G) additional searchers to clear every edge of G2 . We can repeat this process to clear all the remaining contaminated edges of GP if |V (P )| ≥ 3. If G is Eulerian and P contains only one edge, then τ (G) = 1 and |V (P )| = 2, and so, from Lemma 2, we have fs(GP ) ≥ 21 |Vodd (GP )| + 2 = |V (G)| + τ (G)|V (P )|. Thus fs(GP ) = |V (G)| + τ (G)|V (P )|. A subset E ′ of the edge set of a connected graph G is an edge cut of G, if G − E ′ is disconnected. We now use an edge cut to give a lower bound on the fast search number.

Y. Xue, B. Yang / Discrete Applied Mathematics (

)

–

5

Theorem 8. Let G be a connected graph and Eχ be an edge cut of G such that the graph G − Eχ consists of two connected components G1 and G2 . If each edge of Eχ connects a vertex of V (G1 ) to a vertex of V (G2 ), then fs(G) ≥ fs(G1 + Eχ ) + fs(G2 + Eχ ) − |Eχ |. Proof. Let S be an optimal fast search strategy of G. We first consider the graph G1 + Eχ . We modify S to obtain a fast search strategy S1 that can clear G1 + Eχ in the following way: We first delete all actions from S that are related only to G2 , i.e., ‘‘placing a searcher on a vertex of G2 ’’ or ‘‘sliding a searcher along an edge of G2 ’’; for each edge v1 v2 of Eχ with v1 ∈ V (G1 ) and v2 ∈ V (G2 ), if it is cleared by the action of ‘‘sliding a searcher from v2 to v1 ’’ in S , then immediately before this sliding action, we insert a new placing action, i.e., ‘‘placing a searcher on v2 ’’. Let m1 be the total number of new placing actions added to S1 . We now show how to use S1 to clear G1 + Eχ . Considering an edge v1 v2 ∈ Eχ with v1 ∈ V (G1 ) and v2 ∈ V (G2 ), if it is cleared by sliding a searcher from v2 to v1 in S , since we have inserted the action of placing a searcher on v2 in S1 , then the searcher can be used to clear v1 v2 by sliding from v2 to v1 . Further, in S1 , since we keep all sliding actions of S on edges of G1 + Eχ , we know G1 + Eχ can be cleared in the same way as in S . Therefore, S1 can clear G1 + Eχ . Similarly, we can also modify the fast search strategy S to obtain a fast search strategy S2 that can clear G2 + Eχ . Let m2 be the total number of new placing actions added to S2 . From the above, we know that the total number of searchers used to clear G1 + Eχ and G2 + Eχ is fs(G) + m1 + m2 . Thus, fs(G1 + Eχ ) + fs(G2 + Eχ ) ≤ fs(G) + m1 + m2 . It is easy to see that m1 is the number of edges in Eχ that are cleared by sliding actions in S from G2 to G1 , and m2 is the number of edges in Eχ that are cleared by sliding actions in S from G1 to G2 . Since every edge of Eχ can be traversed exactly once, we have |Eχ | = m1 + m2 . Therefore, fs(G1 + Eχ ) + fs(G2 + Eχ ) ≤ fs(G) + |Eχ |. 3.2. Cartesian products of Eulerian graphs and paths Recall that Bm is an Eulerian graph with m ≥ 3 vertices and Pn is a path with n vertices. We will use Gm×n to denote Bm Pn . j Let vi,j denote a vertex of Gm×n , which corresponds to the vertex vi on Bm and the vertex vj on Pn . So we use Bm , 1 ≤ j ≤ n, to denote the Eulerian graph in Gm×n with vertex set {v1,j , v2,j , . . . , vm,j } (the jth copy of Bm ). Similarly, we use Pni , 1 ≤ i ≤ m, to denote the path in Gm×n with vertex set {vi,1 , vi,2 , . . . , vi,n } (the ith copy of Pn ). We first give an upper bound on fs(Gm×n ). Lemma 9. For m ≥ 3 and n ≥ 2, fs(Gm×n ) ≤ m + n. Proof. Here is a fast search strategy that clears all edges of Gm×n using m + n searchers. 1. Place a searcher λi on each vertex vi,1 ∈ V (Gm×n ), 1 ≤ i ≤ m, and place a searcher γj on each vertex v1,j ∈ V (Gm×n ), 1 ≤ j ≤ n. 2. Slide γ1 along the Eulerian circuit of B1m to clear all its edges. Let j = 1. j+1

j +1

3. Slide each λi to Bm , 1 ≤ i ≤ m, and then slide γj+1 along the Eulerian circuit of Bm to clear all its edges. If j + 1 = n, then stop; otherwise, j ← j + 1 and repeat step 3. Since the above fast search strategy has m + n placing actions, we know that fs(Gm×n ) ≤ m + n.

For the fast search strategy given in the proof of Lemma 9, each Pni , 1 ≤ i ≤ m, is associated with a searcher, i.e., λi , who j

clears the path, and each Bm , 1 ≤ j ≤ n, is also associated with a searcher, i.e., γj , who clears the Eulerian graph. Note that all λi ’s move in the same orientation simultaneously. We can also arrange all γj ’s to make them move in the same orientation. If this is the only way to clear Gm×n using m + n searchers, it would not be too hard to show the optimality of this strategy. Unfortunately, we also have ‘‘non-typical’’ ways to clear Gm×n using m + n searchers. For example, consider the graph B3 P3 (see Fig. 2), where the B3 is a 3-cycle. Besides the fast search strategy given in the proof of Lemma 9 that can clear B3 P3 using 6 searchers, we can also use the following ‘‘non-typical’’ way to clear B3 P3 using 6 searchers. (1) Place two searchers on v1,2 ; and place one searcher on v1,1 , v2,1 , v2,2 and v1,3 respectively. (2) Slide a searcher from v1,2 to v3,1 along the path v1,2 v1,1 v2,1 v3,1 . (3) Slide a searcher from v1,1 to v3,2 along the path v1,1 v3,1 v3,2 . (4) Slide a searcher from v2,1 to v2,3 along the path v2,1 v2,2 v3,2 v1,2 v2,2 v2,3 . (5) Slide a searcher from v3,2 to v3,3 . (6) Slide a searcher from v1,2 to v1,3 along the path v1,2 v1,3 v2,3 v3,3 v1,3 . Due to the ‘‘non-typical’’ ways to clear Gm×n , we need the following 6 lemmas to show that fs(Gm×n ) = m + n. Lemma 10. For m ≥ 3, fs(Gm×2 ) = m + 2. Proof. From Lemma 9, we have fs(Gm×2 ) ≤ m + 2. Since Gm×2 contains 2m odd vertices, it follows from Lemma 2 that fs(Gm×2 ) ≥ m + 2. Therefore, fs(Gm×2 ) = m + 2.

6

Y. Xue, B. Yang / Discrete Applied Mathematics (

)

–

Fig. 2. Cartesian product of a cycle C3 and a path P3 .

Fig. 3. An instance of G′6×3 .

Fig. 4. An instance of G′6×1 .

In order to obtain a lower bound for fs(Gm×3 ), we need to consider a special graph G′m×1 obtained from Gm×1 . In general, let G′m×n denote a graph obtained from Gm×n by adding a pendant edge to every vertex of Bnm (see Figs. 3 and 4). Since G′m×1 has 2m odd vertices, it follows from Lemma 1 that fs(G′m×1 ) ≥ m. In Lemma 12, we will give a fast search strategy for G′m×1 that uses m searchers. Before that, we need a structure property of the Eulerian subgraph in G′m×1 , which is described in Lemma 11. Let B be an Eulerian graph and a be a vertex of B. Let d = degB (a)/2. We repeat the following process d times until the degree of a is dropped to 0: select a cycle containing a, which has the shortest length among all the cycles containing a, and then remove all the edges of the cycle from B. Let Ca1 , Ca2 , . . . , Cad be the cycles selected in each iteration. The cycle Cad has the following property. Lemma 11. Let a be a vertex of an Eulerian graph B. Let Ca1 , Ca2 , . . . , Cad be the cycles described above. Then Cad contains two j

neighbors of the vertex a which are not contained in any Ca , j < d.

Proof. If d = 1, there is only one cycle containing a; so the lemma is trivial. If d ≥ 2, since Cad contains at least three vertices, j

then let Cad = av1 . . . vk a, k ≥ 2. Suppose that v1 is also contained in another cycle Ca , 1 ≤ j < d. Note that Ca1 , Ca2 , . . . , Cad , j

j

are edge disjoint cycles. So Ca does not contain the edge av1 . Let Ca = avp . . . vq v1 vs . . . vt a. It is easy to see that both cycles av1 vs . . . vt a and avp . . . vq v1 a have shorter lengths than avp . . . vq v1 vs . . . vt a. This is a contradiction. Thus, v1 is contained only in Cad .

Y. Xue, B. Yang / Discrete Applied Mathematics (

)

–

7

Similarly, we can show that vk is only contained in Cad . Therefore, Cad contains two neighbors of the vertex a which are j

not contained in any Ca , 1 ≤ j < d.

From Lemma 11, we can prove the following results. Lemma 12. fs(G′m×1 ) = m. Proof. It follows from Lemma 1 that fs(G′m×1 ) ≥ m. So we only need to describe a fast search strategy that uses m searchers to clear G′m×1 . Let B be the Eulerian graph obtained from G′m×1 by deleting all its leaves. Let a be a vertex that has the minimum degree among all vertices of B, and let d = degB (a)/2. Let u ∈ V (B) be a neighbor of a and Ca1 , Ca2 , . . . , Cad be the cycles in j

Lemma 11 such that u ∈ V (Cad ) and u ̸∈ V (Ca ) for j < d. If d ≥ 2, then let Hu be a connected component that contains u after all edges of ∪1≤i≤d−1 E (Cai ) are deleted from B, and let H u be a subgraph of B obtained from B by deleting all edges of Hu from B. Note that both Hu and H u are Eulerian, and E (Hu ) and E (H u ) form a partition of E (B). If d = 1, then let Hu = B. Now we give a fast search strategy for G′m×1 that uses m searchers.

1. Place a searcher on every leaf of G′m×1 , except the leaf neighbor of u; then slide these searchers to their non-leaf neighbors. Place another searcher on a. If Hu = B, go to Step 3. 2. Note that H u is an Eulerian subgraph, in which a is occupied by two searchers and each other vertex is occupied by one searcher. Slide one of the two searchers on a from a to itself along all edges of H u . 3. Note that Hu is an Eulerian subgraph with degHu (a) = 2, in which a is occupied by two searchers, u is not occupied, and each other vertex is occupied by one searcher. Slide one of the two searchers on a from a to u along the edge au, and slide the other searcher from a to u along all edges of Hu except the edge au. After Hu is cleared, slide one searcher from u to its leaf neighbor on G′m×1 . Since only m searchers are placed on G′m×1 in Step 1, the above strategy clears G′m×1 using m searchers.

Lemma 13. Each optimal fast search strategy of G′m×1 satisfies the following properties: (i) the first cleared edge is cleared by sliding a searcher from a leaf to its neighbor; and (ii) the last cleared edge is cleared by sliding a searcher from a non-leaf vertex to its leaf neighbor. Proof. Note that G′m×1 contains 2m odd vertices and fs(G′m×1 ) = m. From the observation in [8], we know that in any fast search strategy, an odd vertex must contain a searcher either before the first sliding action or after the last sliding action. So, in any optimal fast search strategy for G′m×1 , every vertex contains exactly one searcher either before the first sliding action or after the last sliding action. For each vertex vi,1 , 1 ≤ i ≤ m, which contains a searcher before the first sliding action, the searcher cannot move because vi,1 has three contaminated edges incident on it. Thus, the first cleared edge of G′m×1 must be cleared by sliding a searcher from a leaf to its neighbor. We now consider the last sliding action that leaves G′m×1 cleared. If the last action is sliding a searcher from a leaf vj,2 to its non-leaf neighbor vj,1 , 1 ≤ j ≤ m, then we know vj,1 must contain at least two searchers after the last action. This contradicts the fact that every vertex contains at most one searcher after the last sliding action. Therefore, the last cleared edge must be cleared by sliding a searcher from a non-leaf vertex to its leaf neighbor. From Theorem 8, Lemmas 4, 10, 12 and 13, we can prove the following result. Lemma 14. For m ≥ 3, fs(G′m×3 ) = m + 3. Proof. Recall that G′m×3 is a graph obtained from Bm P3 by adding a pendant edge to every vertex of B3m (see Fig. 3). Let G′m×1 be the subgraph of G′m×3 which contains B1m (see Fig. 4) and G′′m×2 be the subgraph of G′m×3 after deleting all edges on B1m j

(see Fig. 5). Recall that Bm , 1 ≤ j ≤ 3, is an Eulerian graph with vertex set {v1,j , v2,j , . . . , vm,j }. For convenience, we will use vi,4 , 1 ≤ i ≤ m, to denote the leaf neighbor of vertex vi,3 . Note that G′′m×2 is the graph obtained from Gm×2 by adding a pendant edge to every odd vertex of Gm×2 . From Lemmas 4 and 10, we have fs(G′′m×2 ) = fs(Gm×2 ) = m + 2. So it follows from Theorem 8 and Lemma 12 that fs(G′m×3 ) ≥ fs(G′′m×2 ) + fs(G′m×1 ) − m = m + 2. For the sake of contradiction, we assume that fs(G′m×3 ) = m + 2. Then let SG′ be an optimal fast search strategy of G′m×3 that uses m + 2 searchers. Note that all placing actions in SG′

m×3

m×3

take place before all sliding actions. So each odd vertex

of G′m×3 contains at least one searcher either before the first sliding action or at the end of SG′

m×3

. Thus, Vodd (G′m×3 ) should

contain at least m searchers at the beginning or at the end. If Vodd (Gm×3 ) contains at least m searchers at the end of SG′ ′

then, using the method in the proof of Theorem 4.4 in [15], we can reverse the strategy

SG′

m×3

m×3

,

so that Vodd (Gm×3 ) contains at ′

least m searchers initially. So we can assume that Vodd (G′m×3 ) contains m searchers before the first sliding action in SG′

m×3

.

Note that the edge set {vi,1 vi,2 | 1 ≤ i ≤ m} is an edge cut of G′m×3 . We can modify the strategy SG′ , using the method m×3 described in the first paragraph of the proof of Theorem 8, to obtain two separate fast search strategies SG′ and SG′′ for m×1

m×2

8

Y. Xue, B. Yang / Discrete Applied Mathematics (

)

–

Fig. 5. An instance of G′′6×2 .

G′m×1 and G′′m×2 , respectively. Since {vi,1 vi,2 | 1 ≤ i ≤ m} contains m edges, we need to add m additional placing actions to and SG′′ . Because fs(G′m×1 ) = m and fs(G′′m×2 ) = m + 2, and SG′′ . Totally, 2m + 2 searchers are used in SG′ obtain SG′ m×2 m×1 m×2 m×1 ′′ ′ uses exactly m searchers uses at least m + 2 searchers. Therefore, SG′ uses at least m searchers and SG we know SG m×1 m×2 m×1 and SG′′ are both optimal. We can assume that all and SG′′ uses exactly m + 2 searchers, which also means that SG′ m×2 m×1 m×2 and SG′′ are carried out before all sliding actions. placing actions in SG′ m×1

m×2

From Lemma 13, the optimal fast search strategy SG′

m×1

must have the following properties: The first cleared edge of

G′m×1 must be cleared by sliding a searcher from a leaf, say vi1 ,2 , to its neighbor vi1 ,1 ; and the last cleared edge of G′m×1 must be cleared by sliding a searcher from a non-leaf vertex, say vi2 ,1 , to its leaf neighbor vi2 ,2 . Since G′m×1 and G′′m×2 share each edge vi,1 vi,2 , 1 ≤ i ≤ m, we know SG′ must share the sliding action and SG′′ m×2 m×1 must satisfy the following conditions: The first cleared edge in the set on each edge vi,1 vi,2 , 1 ≤ i ≤ m. Thus SG′′ m×2

{vi,1 vi,2 | 1 ≤ i ≤ m} must be cleared by sliding a searcher from vi1 ,2 to vi1 ,1 ; and the last cleared edge in the set {vi,1 vi,2 | 1 ≤ i ≤ m} must be cleared by sliding a searcher from vi2 ,1 to vi2 ,2 . From the assumption for SG′ , we know that Vodd (G′′m×2 ) contains at least m searchers before the first sliding action in m×3 SG′′

m×2

. Thus, B2m and B3m contain at most two searchers before the first sliding action of SG′′

m×2

least one searcher before the first sliding action of SG′′

m×2

. Moreover, B2m should contain at

. This is because the first cleared edge in the set {vi,1 vi,2 | 1 ≤ i ≤ m}

is cleared by sliding a searcher from vi1 ,2 to vi1 ,1 . If B2m does not contain any searcher before the first sliding action, then we know no searcher can slide from vi1 ,2 to vi1 ,1 . Suppose that B2m contains two searchers before the first sliding action of SG′′ . m×2 One of the following two cases must happen. Case 1. There are two vertices of B2m , each of which contains one searcher before the first sliding action of SG′′ . It is m×2 easy to see that the two searchers cannot move until another searcher slides to them. We also know that each searcher placed on vj,1 , 1 ≤ j ≤ m, cannot move until a searcher slides from vi1 ,2 to vi1 ,1 . Searchers that are placed on a subset of {vj,4 | 1 ≤ j ≤ m} can slide to B3m . However, they would be stuck on B3m since B3m contains no searchers. Thus, no edges between B2m and B3m can be cleared, which is a contradiction. Case 2. There is a vertex vk,2 , 1 ≤ k ≤ m, of B2m that contains two searchers before the first sliding action of SG′′ . Then m×2 we have three subcases. Case 2.1. The first cleared edge incident on vk,2 is cleared by sliding one of the two searchers from vk,2 to vk,1 (in this case, k = i1 ). After this action, the other searcher contained in vk,2 cannot move until another searcher slides to vk,2 . Further, since all the vertices of B2m and B3m except vk,2 contain no searcher initially, we know searchers sliding from vi,1 to vi,2 , 1 ≤ i ≤ m, or from vj,4 to vj,3 , 1 ≤ j ≤ m, are stuck on B2m or B3m respectively. Thus, no edges between B2m and B3m can be cleared. This is a contradiction. Case 2.2. The first cleared edge incident on vk,2 is cleared by sliding one of the two searchers from vk,2 to vk,3 . After this action, the other searcher contained in vk,2 cannot move until another searcher slides to vk,2 . If a searcher slides from vj,3 to vj,2 , 1 ≤ j ≤ m and j ̸= k, then we know the searcher must be stuck on vj,2 since then. Note that the first cleared edge between B2m and B1m is cleared by sliding a searcher from vi1 ,2 to vi1 ,1 . But no searcher can slide from vi1 ,2 to vi1 ,1 . This is a contradiction. Case 2.3. The first cleared edge incident on vk,2 is cleared by sliding one of the two searchers from vk,2 to vk′ ,2 , which is a neighbor of vk,2 on B2m . Similar to Case 1, no edges between B2m and B3m can be cleared, which brings a contradiction. Therefore, B2m must contain exactly one searcher before the first sliding action of SG′′ . Further, B3m also contains exactly m×2

one searcher before the first sliding action of SG′′

m×2

; otherwise, no searcher can slide from B3m to B2m . Note that the remaining

m searchers are placed on m odd vertices of G′′m×2 respectively. Since each leaf contains at most one searcher all the time in an optimal strategy, we know these m searchers are placed on m distinct odd vertices of G′′m×2 .

Y. Xue, B. Yang / Discrete Applied Mathematics (

Before the first sliding action of SG′′

m×2

)

–

9

, let vℓ1 ,2 be a vertex of B2m that contains a searcher, and let vℓ2 ,3 be a vertex of B3m

that contains a searcher. Since both deg(vℓ1 ,2 ) and deg(vℓ2 ,3 ) are at least 4, each of vℓ1 ,2 and vℓ2 ,3 will be occupied by at least one searcher throughout SG′′ . Note that all other m searchers will stop on the m leaves of G′′m×2 , on which no searchers are m×2

, B2m contains exactly one searcher that occupies vℓ1 ,2 , and contains exactly one searcher that occupies vℓ2 ,3 . If no searcher slides from vℓ1 ,3 to vℓ1 ,2 , then searchers sliding from B3m to B2m would be stuck on B2m and no searcher can clear the edge vi1 ,2 vi1 ,1 . Thus the edge vℓ1 ,2 vℓ1 ,3 is cleared by sliding a searcher from vℓ1 ,3 to vℓ1 ,2 . Similarly, the edge vℓ2 ,3 vℓ2 ,4 is cleared by sliding a searcher from vℓ2 ,4 to vℓ2 ,3 ; otherwise, searchers sliding from a subset of {vj,4 | 1 ≤ j ≤ m} to B3m would be stuck on B3m . Let t denote the moment just after the last contaminated edge, i.e., vi2 ,1 vi2 ,2 , in {vi,1 vi,2 | 1 ≤ i ≤ m} is cleared. Since the edge vi2 ,1 vi2 ,2 is cleared by sliding a searcher from vi2 ,1 to vi2 ,2 , we know that at the moment t , vi2 ,2 should contain at least placed before the first sliding action of SG′′

m×2

. Hence, at the end of SG′′

m×2

B3m

one searcher. If all edges between B2m and B3m are cleared at the moment t , B2m would contain at least two searchers at the end because vℓ1 ,2 always contains a searcher throughout SG′′m×2 . This is a contradiction. If there are edges between B2m and B3m that are not cleared at the moment t, we have two cases. Case 1. All edges of B2m are cleared at t. Then vi2 ,2 contains two searchers at t. We have two subcases: Case 1.1. i2 = ℓ1 . Because the edge vℓ1 ,2 vℓ1 ,3 is cleared by sliding a searcher from vℓ1 ,3 to vℓ1 ,2 , the searchers contained in vi2 ,2 cannot slide to B3m along vi2 ,2 vi2 ,3 . Since all edges of B2m are cleared, we know vi2 ,2 would contain at least two searchers at the end of SG′′ , which is a contradiction. m×2

Case 1.2. i2 ̸= ℓ1 . Since all edges of B2m are cleared, there is at most one contaminated edge incident on vi2 ,2 . Thus, vi2 ,2 must contain at least one searcher at the end of SG′′ . This is also a contradiction. m×2

Case 2. There are edges of B2m that are not cleared at t. Consider a sliding action that leaves all edges of B2m cleared. Let vj1 ,2 vj2 ,2 denote the last cleared edge of B2m which is cleared by sliding a searcher from vj1 ,2 to vj2 ,2 . Then vj2 ,2 contains two searchers at the moment when vj1 ,2 vj2 ,2 becomes cleared. If j2 = ℓ1 , vj2 ,2 would contain two searchers at the end since the edge vj2 ,2 vj2 ,3 must be cleared by sliding a searcher from vj2 ,3 to vj2 ,2 . This is a contradiction. If j2 ̸= ℓ1 , since the edge vj2 ,2 vj2 ,1 has been cleared, we know that vj2 ,2 would contain a searcher at the end, which is a contradiction. From the above, we know fs(G′m×3 ) ≥ m + 3. Therefore, from Lemmas 9 and 4, we have fs(G′m×3 ) = m + 3. Lemma 15. For m ≥ 3 and n ≥ 2, fs(Gm×n ) ≥ m + n. Proof. If n = 2, it follows from Lemma 10 that fs(Gm×2 ) = m + 2. If n = 3, from Lemmas 4 and 14, we have fs(Gm×3 ) = fs(G′m×3 ) = m + 3. We now suppose that n ≥ 4. If n is odd, then we can decompose Gm×n into one Gm×3 and (n − 3)/2 copies of Gm×2 (see Fig. 6). From Theorem 8, we have fs(Gm×n ) ≥ fs(G′m×3 ) + fs(G′m×(n−3) ) − m

≥ m + 3 + fs(G′′m×2 ) + fs(G′m×(n−5) ) − 2m 1

1

2

2

≥ m + 3 + (n − 3)(m + 2) − (n − 3)m = m + n. If n is even, then we decompose Gm×n into n/2 copies of Gm×2 (see Fig. 7). Similar to the above case, we have fs(Gm×n ) ≥

1 2

n(m + 2) −

1 2

n − 1 m = m + n.

Therefore, fs(Gm×n ) ≥ m + n when n ≥ 2.

From Lemmas 9 and 15, we have the main result of this section. Theorem 16. For m ≥ 3 and n ≥ 2, fs(Bm Pn ) = m + n. 3.3. Variants of Bm Pn j

From the proofs in Section 3.2, we know that even if each Eulerian graph Bm , 1 ≤ j ≤ n, is replaced by an arbitrary Eulerian graph with m vertices (all these Eulerian graphs may be different), we can still prove the same results. This means Theorem 16 holds for a larger class of graphs including all Bm Pn . j

Theorem 17. Let Wm,n be a graph obtained from Bm Pn (m ≥ 3, n ≥ 2) by replacing each Eulerian graph Bm (1 ≤ j ≤ n) by an arbitrary Eulerian graph with m vertices. Then fs(Wm,n ) = m + n.

10

Y. Xue, B. Yang / Discrete Applied Mathematics (

)

–

Fig. 6. Decomposition of G6×5 into G6×2 and G6×3 .

Fig. 7. Decomposition of G6×6 into three copies of G6×2 .

Fig. 8. An instance of Z6×2 .

We now consider another variant of the Cartesian product Bm Pn . For every Bim on Bm Pn , 1 ≤ i ≤ n, we select a vertex vxi ,i , 1 ≤ xi ≤ m. We then add an edge between vxi ,i and vxi+1 ,i+1 for every i = 1, . . . , n − 1. Let the new graph denoted by Zm×n (see Fig. 8). Lemma 18. For m ≥ 3 and n ≥ 2, fs(Zm×n ) = m + 1.

Y. Xue, B. Yang / Discrete Applied Mathematics (

Proof. From Lemma 2, we have fs(Zm×n ) ≥ searchers to clear Zm×n .

1 V 2 odd

)

–

11

(Zm×n ) + 2 = m + 1. The following is a fast search strategy that uses m + 1

1. Place a searcher λi on each vertex vi,1 ∈ V (Zm×n ), 1 ≤ i ≤ m, and place a searcher γ on the vertex vx1 ,1 . 2. Slide γ along the edges of the Eulerian graph B1m to clear all its edges. Let j = 1. j +1

3. Slide γ to vxj+1 ,j+1 along the edge vxj ,j vxj+1 ,j+1 , and slide each λi to Bm , 1 ≤ i ≤ m. Then slide γ along the edges of the Eulerian graph

j+1 Bm

to clear all its edges. If j + 1 = n, then stop; otherwise, j ← j + 1 and repeat step 3.

It is easy to see that the lower bound and the fast search strategy in the proof of Lemma 18 can also be applied to the graph Wm′ ,n defined in the following corollary. j

Corollary 19. Let Wm′ ,n be a graph obtained from Zm×n (m ≥ 3, n ≥ 2) by replacing each Eulerian graph Bm (1 ≤ j ≤ n) by an arbitrary Eulerian graph with m vertices. Then fs(Wm′ ,n ) = m + 1. Note that by adding a path with n vertices to Bm Pn , the fast search number of the new graph Zm×n is greatly reduced compared to fs(Bm Pn ). This demonstrates that the fast searching problem is not subgraph-closed. 4. Hypercubes and toroidal grids In this section, we investigate the fast search number of hypercubes and the fast search number of toroidal grids. Let Qk , k ≥ 0, denote a k-dimensional hypercube. Theorem 20. If k is odd and k ≥ 3, then fs(Qk ) = 2k−1 + 2. Proof. Note that Qk has 2k vertices and every vertex has degree k. Since k is odd and k ≥ 3, we know that Qk−1 is an Eulerian graph with 2k−1 vertices. It follows from Theorem 16 that fs(Qk ) = fs(Qk−1 P2 ) = 2k−1 + 2. Observe that Qk = Qk−2 Q2 = Qk−2 C4 and Qk−2 is an Eulerian graph when k is even and k ≥ 4. This motivates us to consider fs(Bm Cn ), where Bm is an Eulerian graph with m vertices. Although Bm Cn is a simple extension of Bm Pn which was considered in the previous section, it turns out to be much more difficult to find a nontrivial lower bound on fs(Bm Cn ). We first give an upper bound on fs(Bm Cn ). Lemma 21. If m ≥ 3 and n ≥ 3, then fs(Bm Cn ) ≤ 2m + n − 2. Proof. Let vi,j denote a vertex of Bm Cn , which corresponds to the vertex vi on Bm and the vertex vj on Cn , and let j

Bm , 1 ≤ j ≤ n, denote the Eulerian graph in Bm Cn with vertex set {v1,j , v2,j , . . . , vm,j }. The following is a fast search strategy that clears Bm Cn using 2m + n − 2 searchers. (1) For B1m , place two searchers on each vi,1 , 1 ≤ i ≤ m. j

(2) For each Bm , 2 ≤ j ≤ n − 1, place one searcher on v1,j . (3) Since B1m is an Eulerian graph, slide a searcher from v1,1 to itself along all edges of B1m . (4) After Step (3), each vertex of B1m still contains two searchers, and all its edges are cleared. So for each vertex vi,1 , 1 ≤ i ≤ m, we can slide one searcher from vi,1 to its neighbor on B2m , and slide the other searcher from vi,1 to its neighbor on Bnm , along the edge between them. (5) After Step (4), each vertex of B2m contains one searcher, except v1,2 , which contains two searchers. First slide a searcher from v1,2 to itself along all edges of B2m , and then slide a searcher from each vi,2 , 1 ≤ i ≤ m, to its neighbor on B3m along the j

edge between them. Continuing like this (if n ≥ 4), we can clear each Bm , 2 ≤ j ≤ n − 1. Then, slide a searcher from each vi,n−1 , 1 ≤ i ≤ m, to its neighbor on Bnm along the edge between them. (6) After Step (5), each vertex of Bnm contains two searchers. So we can easily slide a searcher from v1,m to itself along all edges of Bnm . From Steps (1) and (2), we know that 2m + n − 2 searchers are placed on Bm Cn . Thus, fs(Bm Cn ) ≤ 2m + n − 2. j

From the above proof, we know that even if each Eulerian graph Bm , 1 ≤ j ≤ n, is any arbitrary Eulerian graph with m vertices, we can still prove the same results. j

Corollary 22. Let Dm,n be a graph obtained from Bm Cn (m ≥ 3, n ≥ 3) by replacing each Eulerian graph Bm (1 ≤ j ≤ n) by an arbitrary Eulerian graph with m vertices. Then fs(Dm,n ) ≤ 2m + n − 2. From the structure of Bm Cn , the fast search strategy described in the proof is essential and the upper bound in Lemma 21 seems hard to beat. But to our surprise, when Bm is a cycle with at least four vertices, we can use a new technique to improve this upper bound for toroidal grids Cm Cn . Theorem 23. If n ≥ m ≥ 4, then fs(Cm Cn ) ≤ 2m + n − 3.

12

Y. Xue, B. Yang / Discrete Applied Mathematics (

)

–

Fig. 9. C4 Cn . j

Proof. Let ui,j denote a vertex of Cm Cn , which corresponds to the ith vertex of Cm and the jth vertex of Cn . Let Cm , 1 ≤ j ≤ n, denote the cycle u1,j u2,j . . . , um,j u1,j (the jth copy of Cm in Cm Cn ). We now give a fast search strategy that uses 2m + n − 3 searchers to clear Cm Cn (see Fig. 9). 1 (1) For Cm , place two searchers on u1,1 , one searcher on u2,1 , and three searchers on um,1 ; if m ≥ 5, place two searchers on each ui,1 , 4 ≤ i ≤ m − 1. j

2 (2) For Cm , place two searchers on u3,2 ; and for each Cm , 3 ≤ j ≤ n − 1, place one searcher on u3,j . (3) Slide a searcher from um,1 to u2,1 along the path um,1 u1,1 u2,1 . 1 (4) After Step (3), each vertex of Cm , except u3,1 , contains two searchers. Slide a searcher from each ui,1 , 1 ≤ i ≤ m and 2 i ̸= 3, to its neighbor on Cm along the edge between them. 2 (5) After Step (4), each vertex of Cm contains one searcher, except u3,2 that contains two searchers. First slide a searcher 2 from u3,2 to itself along all edges of Cm , and then slide this searcher from u3,2 to u3,1 along the edge between them. 1 2 2 (6) After Step (5), each vertex of Cm and Cm contains exactly one searcher. Since all edges of Cm are cleared, slide a searcher 3 from each ui,2 , 1 ≤ i ≤ m, to its neighbor on Cm along the edge between them. 3 (7) Since each vertex of Cm contains one searcher, except u3,3 , which contains two searchers, slide a searcher from u3,3 to 3 4 itself along the edges of Cm . Then slide a searcher from each ui,3 , 1 ≤ i ≤ m, to its neighbor on Cm along the edge between j

them. Continuing like this we can clear each Cm , 3 ≤ j ≤ n − 1. After that, slide a searcher from each ui,n−1 , 1 ≤ i ≤ m, to n its neighbor on Cm along the edge between them. 1 n (8) After Step (7), each vertex of Cm and Cm contains exactly one searcher. From Step (3), we know that u1,1 has only one contaminated edge, i.e., u1,1 u1,n , incident on it. So, slide the searcher on u1,1 to u1,n along this edge, and then slide this n searcher from u1,n to itself along the edges of Cm . 1 (9) Slide a searcher from each ui,n , 2 ≤ i ≤ m, to its neighbor on Cm along the edge between them. After this, each vertex 1 of Cm , except u1,1 , contains two searchers. Slide a searcher from u2,1 to um,1 along the path u2,1 u3,1 . . . um,1 . Now every edge of Cm Cn is cleared. 2 1 , and one searcher From Steps (1) and (2), we know that 2(m − 1) searchers are placed on Cm , 2 searchers are placed on Cm j

is placed on each Cm , 3 ≤ j ≤ n − 1. In total, 2m + n − 3 searchers are placed on Cm Cn . Therefore, fs(Cm Cn ) ≤ 2m + n − 3.

We now consider the upper bound of fs(Qk ) when k is even. Since Qk = Qk−2 C4 and Qk−2 is an Eulerian graph when k is even and k ≥ 4, it follows from Lemma 21 that fs(Qk ) ≤ 2k−1 + 2. In the following theorem, we improve this upper bound using a strategy similar to the one described in the proof of Theorem 23. Theorem 24. If k is even and k ≥ 4, then fs(Qk ) ≤ 2k−1 + 1. Proof. If k = 4, then from Theorem 23 we have fs(Q4 ) ≤ 9, and so the theorem is proved. Suppose that k ≥ 6 and k is (i,j) even. We observe that Qk = Qk−4 Q4 = Qk−4 C4 C4 . Let Qk−4 , 1 ≤ i, j ≤ 4, denote a copy of Qk−4 in C4 C4 (see Fig. 10). (1,j)

(j)

(2,j)

(3,j)

(4,j)

Let Qk−2 , 1 ≤ j ≤ 4, denote a copy of Qk−2 in Qk which is induced by the vertices of Qk−4 , Qk−4 , Qk−4 , and Qk−4 . We now describe a fast search strategy that clears Qk using 2k−1 + 1 searchers. (1,1) (2,1) (1) Place two searchers on each vertex of Qk−4 ; place one searcher on each vertex of Qk−4 , place three searchers on each (4,1)

(3,2)

(3)

vertex of Qk−4 ; place two searchers on each vertex of Qk−4 ; and place an additional searcher on just one vertex of Qk−2 . all

(1,1) (2) For Qk−4 , slide a searcher (1,1) edges of Qk−4 are cleared.

from one of its vertices along all its edges and back to this vertex. At the end of this step, (4,1)

(1,1)

(2,1)

(3) Slide a searcher from each vertex of Qk−4 to its neighbor on Qk−4 , and then slide further to a new neighbor on Qk−4 . At the end of this step, each vertex of

(1,1) (2,1) Qk−4 , Qk−4

and

(4,1) Qk−4

contains two searchers.

Y. Xue, B. Yang / Discrete Applied Mathematics (

)

–

13

(i,j)

Fig. 10. Qk = Qk−4 Q4 : the vertex Q(i, j), 1 ≤ i, j ≤ 4, represents Qk−4 .

(1,1)

(2,1)

(4,1)

(2)

(4) Slide a searcher from each vertex of Qk−4 , Qk−4 and Qk−4 to its neighbor on Qk−2 along the edge between them.

(3,2) (2) (5) Slide a searcher from a vertex of Qk−4 along all the edges of Qk−2 and back to this vertex. Then slide a searcher from (3,2) (3,1) each vertex of Qk−4 to its neighbor on Qk−4 along the edge between them. (1) (2) (2) (6) After Step (5), each vertex of Qk−2 and Qk−2 contains exactly one searcher. Since all edges of Qk−2 are cleared, slide a (2) (3) searcher from each vertex of Qk−2 to its neighbor on Qk−2 along the edge between them. (3) (7) First slide the additional searcher placed in Step (1) along all edges of Qk−2 to clear them, and then slide a searcher (3) (4) from each vertex of Qk−2 to its neighbor on Qk−2 along the edge between them. (1) (4) (8) After Step (7), each vertex of Qk−2 and Qk−2 contains exactly one searcher. From Steps (2) and (3), we know that each (1,1) (1,1) vertex of Qk−4 has only one contaminated edge incident on it. So, slide a searcher from each vertex of Qk−4 to its neighbor (1,4) on Qk−4 along the edge between them. (4) (1,4) (4) (9) For Qk−2 , slide a searcher from one of the vertices on Qk−4 along all edges of Qk−2 . Then slide a searcher from each (i,4) (1) vertex of Qk−4 , 2 ≤ i ≤ 4, to its neighbor on Qk−2 along the edge between them. (i,1) (10) For each of Qk−4 , 2 ≤ i ≤ 4, slide one searcher from one of its vertices along all its edges and back to this vertex. At (i,1) the end of this step, all edges of Qk−4 , 2 ≤ i ≤ 4, are cleared. (2,1) (3,1) (11) Slide a searcher from each vertex of Qk−4 to its neighbor on Qk−4 , and then slide further to a new neighbor on (4,1) Qk−4 . At the end of this step, every edge of Qk is cleared. (1) (2) From Step (1), we know that 3 · 2k−3 searchers are placed on Qk−2 , 2k−3 searchers are placed on Qk−2 , and one additional (3) searcher is placed on Qk−2 . In total, 2k−1 + 1 searchers are placed on Qk . Therefore, fs(Qk ) ≤ 2k−1 + 1.

Applying the same idea as that used in the proof of Theorem 24, we can show the following. Corollary 25. For m ≥ 3, fs(Bm Q4 ) ≤ 8m + 1. Similar to Corollary 22, we can extend Corollary 25 to a broader class of graphs. Corollary 26. Let Qm,n be a graph obtained from Bm Q4 (m ≥ 3) by replacing each copy of Bm by an arbitrary Eulerian graph with m vertices. Then fs(Qm,n ) ≤ 8m + 1. Recall that a graph is even if every vertex has an even degree, and it is odd if every vertex has an odd degree. Corollary 27. Let n ≥ 6 and H be a graph with m vertices. If n and H are even, or n and H are odd, then fs(H Qn ) ≤ m2n−1 + 1. If one of n and H is even and the other is odd, then fs(H Qn ) = m2n−1 + 2. Proof. If n is even and H is an even graph, then H Qn−4 is Eulerian since n ≥ 6. Similarly, if n is odd and H is an odd graph, then H Qn−4 is also Eulerian. Thus, from Corollary 25, we have fs(H Qn ) = fs(H Qn−4 Q4 ) ≤ 8m2n−4 + 1 = m2n−1 + 1. If one of n and H is even and the other is odd, then H Qn−1 is Eulerian. So, it follows from Theorem 16 that fs(H Qn ) = fs(H Qn−1 Q1 ) = m2n−1 + 2. Before giving a lower bound for fs(Qk ) when k is even, we first consider the treewidth of Qk . Given a graph G = (V , E ), a tree decomposition of G is a pair (T , W ) with a tree T = (I , F ), I = {1, 2, . . . , m}, and a family of non-empty subsets W = {Wi ⊆ V : i = 1, 2, . . . , m}, satisfying that

m

1. i =1 W i = V , 2. for each uv ∈ E, there is an i ∈ I with {u, v} ⊆ Wi , and 3. for all i, j, k ∈ I, if j is on the path from i to k in T , then Wi Wk ⊆ Wj .

14

Y. Xue, B. Yang / Discrete Applied Mathematics (

)

–

The width of (T , W ) is max{|Wi | − 1 : 1 ≤ i ≤ m}. The treewidth of G, denoted by tw(G), is the minimum width over all tree decompositions of G. A tree decomposition (T , W ) is a path decomposition if T is a path; the pathwidth of a graph G, denoted by pw(G), is the minimum width over all path decompositions of G. From [6], we have the following lower bound for tw(Qk ). Lemma 28 ([6]). There is a constant k0 such that, for any k ≥ k0 , tw(Qk ) ≥

12√ ·2k . 25 k

Since fs(G) ≥ pw(G) ≥ tw(G), we have the following result (we rewrite the lower bound in a power of 2 so that it can be easily compared with the upper bound of fs(Qk ) when k is even). Corollary 29. There is a constant k0 such that fs(Qk ) ≥

√ 3 k+2−log 2 25

k

for any k ≥ k0 .

5. Open problems We conclude this paper by listing some open problems that we consider worth to investigate. (1) For toroidal grids Cm Cn (n ≥ m ≥ 4), we proved that fs(Cm Cn ) ≤ 2m + n − 3. We conjecture that 2m + n − 3 is also a lower bound when n ≥ m ≥ 4. We also conjecture that fs(Bm Cn ) ≥ 2m + n − 3,√n ≥ m ≥ 4. 3 k+2−log k 2 for large k. We conjecture that (2) We proved that fs(Qk ) ≤ 2k−1 + 1 when k is even and fs(Qk ) ≥ 25 k−1 fs(Qk ) = 2 + 1 when k is even. (3) In [15], Stanley and Yang showed that fs(Pm Pn ) = m + n − 2 (m ≥ 2, n ≥ 2). We also believe that it would be interesting to consider algorithms for computing fs(Tm Pn ), where Tm is a tree with m vertices and Pn is a path with n vertices. Acknowledgments The authors would like to thank the anonymous referees for their valuable comments and suggestions, which improved the presentation of this paper. We would also like to thank Sandra Zilles for comments and discussions on this paper. The second author’s research was supported in part by an NSERC Discovery Research Grant, Application No.: RGPIN2013-261290. References [1] B. Alspach, Sweeping and searching in graphs: a brief survey, Matematiche 59 (2006) 5–37. [2] D. Bienstock, Graph searching, path-width, tree-width and related problems (a survey), DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 5 (1991) 33–49. [3] D. Bienstock, P. Seymour, Monotonicity in graph searching, J. Algorithms 12 (2) (1991) 239–245. [4] A. Bonato, R.J. Nowakowski, The Game of Cops and Robbers on Graphs, American Mathematical Soc., 2011. [5] A. Bonato, B. Yang, Graph searching and related problems, in: Panos Pardalos, Ding-Zhu Du, Ronald Graham (Eds.), Handbook of Combinatorial Optimization, second ed., Springer, 2013, pp. 1511–1558. [6] L.S. Chandran, T. Kavitha, The treewidth and pathwidth of hypercubes, Discrete Math. 306 (3) (2006) 359–365. [7] D. Dereniowski, Ö.Y. Diner, D. Dyer, Three-fast-searchable graphs, Discrete Appl. Math. 161 (2013) 1950–1958. [8] D. Dyer, B. Yang, Ö Yaşar, On the fast searching problem, in: Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management, in: Lecture notes in Computer Science, vol. 5034, Springer, 2008, pp. 143–154. [9] F.V. Fomin, D.M. Thilikos, An annotated bibliography on guaranteed graph searching, Theoret. Comput. Sci. 399 (3) (2008) 236–245. [10] G. Hahn, Cops, robbers and graphs, Tatra Mt. Math. Publ. 36 (163) (2007) 163–176. [11] L.M. Kirousis, C.H. Papadimitriou, Searching and pebbling, Theoret. Comput. Sci. 47 (1986) 205–218. [12] F.S. Makedon, C.H. Papadimitriou, I.H. Sudborough, Topological bandwidth, SIAM J. Algebr. Discrete Methods 6 (3) (1985) 418–444. [13] N. Megiddo, S.L. Hakimi, M.R. Garey, D.S. Johnson, C.H. Papadimitriou, The complexity of searching a graph, J. ACM 35 (1) (1988) 18–44. [14] T. Parsons, Pursuit-evasion in a graph, in: Proceedings of the International Conference on the Theory and Applications of Graphs, in: Lecture Notes in Mathematics, Springer-Verlag, 1976, pp. 426–441. [15] D. Stanley, B. Yang, Fast searching games on graphs, J. Combin. Optim. 22 (4) (2011) 763–777. [16] Y. Xue, B. Yang, F. Zhong, S. Zilles, Fast searching on complete k-partite graphs, in: Proceedings of the International Conference on Combinatorial Optimization and Applications, in: Lecture Notes in Computer Science, vol. 10043, Springer, 2016, pp. 159–174. [17] B. Yang, Fast edge-searching and fast searching on graphs, Theoret. Comput. Sci. 412 (2011) 1208–1219. [18] B. Yang, Fast-mixed searching and related problems on graphs, Theoret. Comput. Sci. 507 (7) (2013) 100–113.