Frédéric Giroire

Dorian Mazauric

Nicolas Nisse

Stéphane Pérennes

Ronan Soares

Connected Surveillance Game

Keywords: surveillance game, cost of connectivity, prefetching, Cops and robber, competitive ratio jeux de surveillance, cout de connectivité, préchargement, Cops and Robbers, ratio de compétitivité

 models the problem of web-page prefetching as a pursuit evasion game played on a graph. This two-player game is played turn-by-turn. The first player, called the observer, can mark a fixed amount of vertices at each turn. The second one controls a surfer that stands at vertices of the graph and can slide along edges. The surfer starts at some initially marked vertex of the graph, her objective is to reach an unmarked node before all nodes of the graph are marked. The surveillance number sn(G) of a graph G is the minimum amount of nodes that the observer has to mark at each turn ensuring it wins against any surfer in G. Fomin et al. also defined the connected surveillance game where the observer must ensure that marked nodes always induce a connected subgraph. They ask what is the cost of connectivity, i.e., is there a constant c > 0 such that the ratio between the connected surveillance number csn(G) and sn(G) is at most c for any graph G. It is straightforward to show that csn(G) ≤ ∆ sn(G) for any graph G with maximum degree ∆. Moreover, it has been shown that there are graphs G for which csn(G) = sn(G)+1. In this paper, we investigate the question of the cost of the connectivity. We first provide new non-trivial upper and lower bounds for the cost of connectivity in the surveillance game. More precisely, we present a family of graphs G such that csn(G) > sn(G) + 1. Moreover, we prove that csn(G) ≤ sn(G)

√ n for any n-node graph G. While the gap between these bounds remains huge, it seems difficult to reduce it. We then define the online surveillance game where the observer has no a priori knowledge of the graph topology and discovers it little-by-little. This variant, which fits better the prefetching motivation, is a restriction of the connected variant. Unfortunately, we show that no algorithm for solving the online surveillance game has competitive ratio better than Ω(∆). That is, while interesting by itself, this variant does not help to obtain better upper bounds for the connected variant.

Introduction

In this paper, we study two variants of the surveillance game introduced in [FGJM + 12]. This two-player game involves one Player moving a mobile agent, called surfer, along the edges of a graph, while a second Player, called observer, marks the vertices of the graph. The surfer wins if it manages to reach an unmarked vertex. The observer wins otherwise, i.e., if it manages to mark all nodes before the surfer "escapes".

Surveillance game. More formally, let G = (V, E) be an undirected simple n-node graph, v 0 ∈ V , and k ∈ N * . Initially, the surfer stands at v 0 which is marked and all other nodes are not marked. Then, turn-by-turn, the observer first marks k unmarked vertices and then the surfer may move to a neighbor of her current position. Once a node has been marked, it remains marked until the end of the game. The surfer wins if, at some step, she reaches an unmarked vertex; and the observer wins otherwise. Note that the game lasts at most n k turns. When the game is played on a directed graph, the surfer has to follow arcs when it moves [FGJM + 12]. A k-strategy for the observer from v 0 , or simply a k-strategy from v 0 , is a function σ : V × 2 V → 2 V that assigns the set σ(v, M ) ⊆ V of vertices, |σ(v, M )| ≤ k, that the observer should mark in the configuration (v, M ), where M ⊆ V , v 0 ∈ M , is the set of already marked vertices and v ∈ M is the current position of the surfer. We emphasis that σ depends implicitly on the graph G, i.e., it is based on the full knowledge of G. A k-strategy from v 0 is winning if it allows the observer to win whatever be the sequence of moves of the surfer starting in v 0 . The surveillance number of a graph G with initial node v 0 , denoted by sn(G, v 0 ), is the smallest k such that there exists a winning k-strategy starting from v 0 .

Let us define some notations used in the paper. Let ∆ be the maximum degree of the nodes in G and, for any v ∈ V , let N (v) be the set of neighbors of v. More generally, the neighborhood N (F ) of a set F ⊆ V is the subset of vertices of V which have a neighbor in F . Moreover, we define the closed neighborhood of a set F as N [F ] = N (F ) ∪ F .

As an example, let us consider the following basic strategy: let σ B be the strategy defined by σ B (v, M ) = N (v) \ M for any M ⊆ V , v 0 ∈ M , and v ∈ M . Intuitively, the basic strategy σ B asks the observer to mark all unmarked neighbors of the current position of the surfer. It is straightforward, and it was already shown in [FGJM + 12], that σ B is a winning strategy for any v 0 ∈ V and it easily implies that sn(G, v 0 ) ≤ max{|N (v 0 )|, ∆ -1}.

Web-page prefetching, connected and online variants. The surveillance game has been introduced because it models the web-page prefetching problem. This problem can be stated as follows. A web-surfer is following the hyperlinks in the digraph of the web. The web-browser aims at downloading the web-pages before the web-surfer accesses it. The number of web-pages that the browser may download before the web-surfer accesses another web-page is limited due to bandwidth constraints. Therefore, designing efficient strategies for the surveillance game would allow to preserve bandwidth while, at the same time, avoiding the waiting time for the download of the web-page the web-surfer wants to access.

By nature of the web-page prefetching problem, in particular because of the huge size of the web digraph, it is not realistic to assume that a strategy may mark any node of the network, even nodes that are "far" from the current position of the surfer. For this reason, [FGJM + 12] defines the connected variant of the surveillance game. A strategy σ is said connected if σ(v, M ) ∪ M induces a connected subgraph of G for any M , v 0 ∈ M ⊆ V (G). Note that the basic strategy σ B is connected. The connected surveillance number of a graph G with initial node v 0 , denoted by csn(G, v 0 ), is the smallest k such that there exists a winning connected k-strategy starting from v 0 . By definition, csn(G, v 0 ) ≥ sn(G, v 0 ) for any graph G and v 0 ∈ V (G). In [FGJM + 12], it is shown that there are graphs G and v 0 ∈ V (G) such that csn(G, v 0 ) = sn(G, v 0 ) + 1. Only the trivial upper bound csn(G, v 0 ) ≤ ∆ sn(G, v 0 ) is known and a natural question is how big the gap between csn(G, v 0 ) and sn(G, v 0 ) may be [FGJM + 12]. This paper provides a partial answer to this question.

Still the connected surveillance game seems unrealistic since the web-browser cannot be asked to have the full knowledge of the web digraph. For this reason, we define the online surveillance game. In this game, the observer discovers the considered graph while marking its nodes. That is, initially, the observer only knows the starting node v 0 and its neighbors. After the observer has marked the subset M of nodes, it knows M and the vertices that have a neighbor in M and the next set of vertices to be marked depends only on this knowledge, i.e., the nodes at distance at least two from M are unknown. In other words, an online strategy is based on the current position of the surfer, the set of already marked nodes and knowing only the subgraph H of the marked nodes and their neighbors (a more formal definition is postponed to Section 3). By definition, the next nodes marked by such a strategy must be known, i.e., adjacent to an already marked vertex. Therefore, an online strategy is connected. We are interested in the competitive ratio of winning online strategies. The competitive ratio ρ(S) of a winning online strategy S is defined as ρ(S) = max G,v0∈V (G)

S(G,v0)

sn(G,v0) , where S(G, v 0 ) denotes the maximum number of vertices marked by S in G at each turn, when the surfer starts in v 0 . Note that, because any online winning strategy S is connected, csn(G, v 0 ) ≤ ρ(S) sn(G, v 0 ) for any graph G and v 0 ∈ V (G).

Related work

The surveillance game has mainly been studied in the computational complexity point of view. It is shown that the problem of computing the surveillance number is NP-hard in split graphs [FGJM + 12]. Moreover, deciding whether the surveillance number is at most 2 is NP-hard in chordal graphs and deciding whether the surveillance number is at most 4 is PSPACE-complete. Polynomial-time algorithms that compute the surveillance number in trees and interval graphs are designed in [FGJM + 12]. All previous results also hold for the connected surveillance number. Finally, it is shown that, for any graph G and

v 0 ∈ V (G), max |N [S]|-1 |S| ≤ sn(G, v 0 ) ≤ csn(G, v 0 )
where the maximum is taken over every subset S ⊆ V (G) inducing a connected subgraph with v 0 ∈ S. Moreover, both previous inequalities turn into an equality in case of trees. [FGJM + 12] asks for an example where the inequalities are strict.

In the literature, there are mainly three types of prefetching: server based hints prefetching [AEFP98, AZN99, Mog96], local prefetching [START_REF] Wang | How far can client-only solutions go for mobile browser speed?[END_REF] and proxy based prefetching [START_REF] Fan | Web prefetching between low-bandwidth clients and proxies: potential and performance[END_REF]. In local prefetching, the client has no aid Inria from the server when deciding which documents to prefetch. In the server based hints prefetching, the server can aid the client to decide which pages to prefetch. Lastly, in the proxy based prefetching, a proxy that connects its clients with the server decides which pages to prefetch. Moreover, some studies consider that the prefetching mechanism has perfect knowledge of the websurfer's behaviour [START_REF] Venkata | Using predictive prefetching to improve world wide web latency[END_REF][START_REF] Thomas | Exploring the bounds of web latency reduction from caching and prefetching[END_REF]. In these studies, the objective is to minimize the waiting time of the web-surfer with a given bandwidth, by designing good prediction strategies for which pages to prefetch. In the context of prefetching web-pages, the surveillance game is a model to study a local prefetching scheme to guarantee that a websurfer never has to wait a web-page to be downloaded, whilst minimizing the bandwidth necessary to achieve such a goal.

Our results

In this paper, we study both the connected and online variants of the surveillance game. First, we try to evaluate the gap between non-connected and connected surveillance number of graphs. We give a new upper bound, independent from the maximum degree, for the ratio csn / sn. More precisely, we show that, for any n-node graph G and any

v 0 ∈ V (G), csn(G, v 0 ) ≤ sn(G, v 0 ) √ n.
Then, we describe a family of graphs G such that csn(G, v 0 ) = sn(G, v 0 ) + 2. Note that, contrary to the simple example that shows that connected and not connected surveillance number may differ by one, a larger difference seems much more difficult to obtain.

As mentioned above, the online variant of the surveillance game is a more constraint version of the connected game. We prove that any online strategy has competitive ratio at least Ω(∆). More formally, we describe a familly of trees with constant surveillance number such that, for any online winning strategy, there is a step when the strategy has to mark at least ∆ 4 vertices in order to win. Unfortunately, this shows that the best (up to constant ratio) online strategy is the basic one.

Cost of connectedness

In this section, we investigate the cost of the connectivity constraint. We first prove the first non-trivial upper bound for the ratio csn / sn. More precisely, we show that for any n-node graph G, csn(G, v 0 ) ≤ sn(G, v 0 ) √ n. Then, we improve the lower bound of [FGJM + 12]. That is, we show a family of graphs where csn(G, v 0 ) > sn(G, v 0 ) + 1. Finally, we disprove a conjecture in [FGJM + 12].

Upper bound

In this section, we give the first non-trivial upper bound (independent from the degree) of the cost of the connectivity in the surveillance game.

Theorem 1. Let G be any connected n-node graph and v

0 ∈ V (G), then csn(G, v 0 ) ≤ sn(G, v 0 ) √ n.
Proof. sn(G, v 0 ) = 1 if and only if G is a path with v 0 as an end. In this case, csn(G, v 0 ) = sn(G, v 0 ) and the result holds.

Let us assume that k = sn(G, v 0 ) > 1. We describe a connected strategy σ marking at most k √ n nodes per turn. Let M 0 = {v 0 } and let M t be the set of vertices marked after t ≥ 1 turns. Assume moreover that M t induces a connected graph of G containing v 0 . Finally, let v t be the vertex occupied by the surfer after turn t. The set σ(v t , M t ) of nodes marked by the observer at step t + 1 is defined as follows. For purpose of contradiction, let us assume that the surfer wins against σ by following the path P = {v 0 , . . . , v t , v t+1 }. That is, at its t + 1 th turn, the surfer moves from a marked vertex v t to an unmarked vertex v t+1 . Therefore, n > tk √ n, otherwise the observer marking k √ n nodes at each turn would have already marked every vertex on the graph by the end of turn t. Moreover, by definition of sigma,

If |V (G) \ M t | ≤ k √ n, then let σ(v t , M t ) = V (G)\M t . Otherwise, let H ∈ V (G)\M t such that |H| = k √ n, H ∪M t induces a connected subgraph and |H ∩ N (v t )| is maximum. Then, σ(v t , M t ) = H, i.e.,
|N (v t ) \ M t | > k √ n
Since, sn(G, v 0 ) = k, let S be any k-winning (non necessarily connected) strategy for the observer. Assume that the observer follows S against the surfer following P \ {v t+1 }. Since, S is winning, all vertices of N (v t ) must be marked after turn t, otherwise the surfer would win by moving to an unmarked neighbor of v t . Therefore, since S can mark at most k vertices each turn, |N (v t )| ≤ kt.

Taking both inequalities, we have that k

2 √ n < |N (v t )| ≤ kt. Hence, 2 √ n < t. Therefore, n > tk 2 √ n > nk, a contradiction.

Lower Bound

This section is devoted to proving the following theorem.

Theorem 2. There exists a family of graphs G and

v 0 ∈ V (G) such that csn(G, v 0 ) > sn(G, v 0 ) + 1.
We use the following result proved in [FGJM + 12]. For any graph G = (V, E) and any vertex v 0 ∈ V , a k-strategy for G with initial vertex v 0 is winning if and only if it is winning against a surfer that is constrained to follow induced paths on G. In other words, the walk of the surfer is contrained to be an induced path.

In the following theorem, by adding a path P = {v 1 , • • • , v r } between two vertices u and v of G, we mean that the induced path P is added as an induced subgraph of G and the edges {u, v 1 } and {v r , v} are added. Let x, α, β and γ be four strictly positive integers satisfying the following

Inria inequations. max{β, β 2 + γ + 1} < α < min{β + γ + 1, 2γ + 2} (1) β < 2γ + 2 (2) 3x ≥ α + β + 2γ + 12 (3) x > 4 5 (α + β + γ) + 10 (4) 2α ≥ 73 + β + 2γ (5)
For instance, x = 250, α = 146, β = 73, γ = 73 are values that satisfy all the above inequalities.

For proving the main theorem in this section we mainly rely in the family of graphs built in the following the procedure described below.

Let G = (V, E) be a graph with 10 isolated vertices {v 0 , w 0 , w 1 , w 2 , w 0 , w 1 , w 2 , s 0 , s 1 , s 2 }. Then, for all i ∈ {0, 1, 2} do the following:

1. 4x -9 vertices of degree one are added and made adjacent to s i ; 2. 3x -2 vertices of degree one are added and made adjacent to w i , respectively 3x -2 neighbors of degree one are added to w i ;

two disjoint paths

A i = {a i 1 , • • • , a i α } and A i = {a i 1 , • • • , a i α } are added between v 0 and s i ; 4. a path B i = {b i 1 , • • • , b i β }
is added between v 0 and w i , and a path

B i = {b i 1 , • • • , b i β } is added between v 0 and w i ; 5. for any j ∈ {i, i+1 mod 3} a path C i,j = {c i,j 1 , • • • , c i,j
γ } is added between s j and w i , and a path C i,j = {c i,j 1 , • • • , c i,j γ } is added between s j and w i ;

6. for any 1 ≤ j ≤ α, 3x -1 vertices of degree one are added and made adjacent to a i j , respectively 3x -1 neighbors of degree one are added to a i j ;

7. for any 1 ≤ j ≤ β, 3x -1 vertices of degree one are added and made adjacent to b i j , respectively 3x -1 neighbors of degree one are added to b i j ;

8. for any 1 ≤ j ≤ γ, ∈ {i, i + 1 mod 3}, 3x -1 vertices of degree one are added and made adjacent to c i, j , respectively 3x -1 neighbors of degree one are added to c i, j .

Hence, the graph G has (30 + 18(α + β) + 36γ)x -29 vertices. Note that, for any i ∈ {0, 1, 2}, the node s i has 4x -3 neighbors, v 0 has 12 neighbors, and any other non-leaf node has degree 3x + 1.

Claim 1. If max{β, β 2 +γ +1} < α < min{β +γ +1, 2γ +2} and β < 2γ +2, the unique (up to symmetries) minimum Steiner-tree for S = N [v 0 ] ∪ {s 0 , s 1 , s 2 } in G has 15 + α + β +

2γ vertices and consists of the vertices of the paths

A 0 , B 1 , C 1,1 , C 1,2 and the vertices in S ∪ {w 1 }.
Proof. The subgraph induced by the vertices of the paths A 0 , B 1 , C 1,1 , C 1,2 and the vertices in S ∪{w 1 } is a subtree spanning S and with 15+α+β +2γ vertices. Let us enumerate all the possible (up to symmetries) Steiner-trees for S.

1. Consider the subgraph induced by the vertices of the paths A 0 , A 1 , A 2 and the vertices in S. The number of vertices is 3α + 13.

Consider the subgraph induced by the vertices of the paths A

0 , A 1 , C 1,1 , C 1,2
and the vertices in S ∪ {w 1 }. The number of vertices is 2α + 2γ + 15.

3. Consider the subgraph induced by the vertices of the paths A 0 , A 1 , B 1 , C 1,2 and the vertices in S ∪{w 1 }. The number of vertices is 2α+β +γ +14.

4. Consider the subgraph induced by the vertices of the paths A 0 , C 0,0 , C 0,1 , C 2,0 , C 2,2 and the vertices in S ∪ {w 0 , w 2 }. The number of vertices is α + 4γ + 17.

5. Consider the subgraph induced by the vertices of the paths B 0 , B 1 , C 0,0 , C 1,1 , C 1,2 and the vertices in S ∪ {w 0 , w 1 }. The number of vertices is 2β + 3γ + 16.

6. Consider the subgraph induced by the vertices of the paths

B 1 , C 1,1 , C 1,2 , C 2,2 , C 2,0 and the vertices in S ∪ {w 1 , w 2 }. The number of vertices is β + 4γ + 17.
If the subgraph induced by the vertices of the paths A 0 , B 1 , C 1,1 , C 1,2 and the vertices in S ∪ {w 1 }, is the unique (up to symmetries) minimum Steiner-tree for S = N [v 0 ] ∪ {s 0 , s 1 , s 2 } in G, then we get the following inequalities: 3 where the scheme of a minimum Steinertree for S = N [v 0 ] ∪ {s 0 , s 1 , s 2 } is depicted with dashed lines.

                   α > β 2 + γ + 1 α > β α > γ + 1 β < 2γ + 2 α < β + γ + 1 α < 2γ + 2. Thus max{β, β 2 + γ + 1} < α < min{β + γ + 1, 2γ + 2} and β < 2γ + 2. The graph G is depicted in Figure
For any i ∈ {0, 1, 2}, let

A i = N [v 0 ] ∪ N [A i ] ∪ N [s i ] (resp., A i = N [v 0 ] ∪ N [A i ] ∪ N [s i ]). Note that |A i | = |A i | = (3α + 4)x + 9 and that the A i and A j , i = j, pairwise intersect only in N [v 0 ]. For any i ∈ {0, 1, 2}, let B i = N [v 0 ]∪N [B i ]∪N [w i ]∪N [C i,i ]∪N [C i,i+1 mod 3 ] ∪ N [s i ] ∪ N [s i+1 mod 3 ] and B i is defined similarly. |B i | = |B i | = (3β + 6γ + 11)x+5. Finally, for any i ∈ {0, 1, 2} and j ∈ {i, i+1 mod 3}, let B i,j = N [v 0 ]∪ N [B i ]∪N [w i ]∪N [C i,j ]∪N [s j ] and B i,j = N [v 0 ]∪N [B i ]∪N [w i ]∪N [C i,j ]∪N [s j ].
Lemma 3. For any i ∈ {0, 1, 2} and j ∈ {i, i + 1 mod 3}, during its first step, any winning (3x + y)-strategy for G must mark at least

• x + 8 -y(α + 1) nodes in A i (resp., in A i ),

and

Inria v 0 s 0 w 0 s 1 w 1 s 2 w 2 α α α β β β γ γ γ γ γ γ Figure 1: Graph Family Scheme.
Here we show only one "layer" of the graph.

• x + 8 -y(β + γ + 2) nodes in B i,j (resp., in B i,j
), and

• 2x + 4 -y(β + 2γ + 3) nodes in B i (resp., in B i ).
Proof. Let S be any winning (3x + y)-strategy and F be the set of nodes that S marks during its first step. Let M = F ∩ A 0 . The surfer goes to a 0 1 . We may assume that S had marked it since the strategy fails otherwise. Now, the surfer first goes to s 0 through A 0 unless, at some turn, its position has an unmarked neighbor. In the latter case, the surfer goes to this unmarked node and wins. During these (α + 1) steps, the strategy S can mark at most (α + 1)(3x + y) extra nodes in A 0 . Hence, in total, at most |M | + (α + 1)(3x + y) nodes have been marked in A 0 when the surfer is at s 0 and it is its turn. Because S is a winning strategy, all nodes in A 0 must have been marked since otherwise the surfer would have won. Therefore,

|M | + (α + 1)(3x + y) ≥ |A 0 \ {v 0 }| = (3α + 4)x + 8 and |M | ≥ x + 8 -y(α + 1).
The proof is similar for

B i,j . Now, let M = F ∩ B 0 and let M = F ∩ (N [v 0 ] ∪ N [B 0 ] ∪ N [w 0 ]) ⊆ M .
The surfer goes to b 0 1 . We may assume that S had marked it since the strategy fails otherwise. Now, the surfer first goes to w 0 through B 0 unless, at some turn, its position has an unmarked neighbor. In the latter case, the surfer goes to this unmarked node and wins. At the turn of the surfer when it is in w 0 , the strategy has marked |M |+(β +1)(3x+y) and all nodes in

N [v 0 ]∪N [B 0 ]∪N [w 0 ] must have been marked. Therefore, at most |M | + (β + 1)(3x + y) -(12 + 3(β + 1)x) = |M | + y(β + 1) -12 nodes of B 0 \ (N [v 0 ] ∪ N [B 0 ] ∪ N [w 0 ])

RR n°8297

Proof. First, let us show that sn(G, v 0 ) ≤ 3x. For this purpose, consider the following strategy. At the first step, the observer marks the 12 neighbors of v 0 and, for any i ∈ {0, 1, 2}, the observer marks x -4 one-degree neighbors of s i .

Note that, all nodes in N (v 0 ) have exactly 3x unmarked neighbors and any vertex has at most 3x + 1 unmarked neighbors. Now, the strategy simply consists in marking at each step the neighbors of the current position of the surfer. Indeed, it is easy to prove by induction on the number of steps that, each time that the surfer arrives at a new node, this node is marked and has at most 3x unmarked neighbors. Now, let us prove that sn(G, v 0 ) > 3x-1. Let S be any (3x-1)-strategy and let F be the set of nodes that S marks during its first step. Clearly, N (v 0 ) ⊆ F since otherwise the surfer wins after its first move. Moreover, because the sets

A i \ N [v 0 ] are pairwise disjoint, there must be i ∈ {0, 1, 2}, such that |F ∩ (A i \ N [v 0 ])| < x -4. Hence, |F ∩ A i | < x + 8
for some i. However, by Lemma 3, any winning (3x -1)-strategy must mark at least x + 8 + α + 1 > x + 8 nodes in each A i during the first step.

Lemma 5. csn(G, v 0 ) > 3x + 1.
Proof. For purpose of contradiction, let us assume that there is a winning connected 3x + 1-strategy. Let F be the set of vertices marked by this strategy during the first step. Clearly, N (v 0 ) ⊆ F and |F | ≤ 3x + 1.

For any 0

≤ i ≤ 2, let f i = |F ∩ N [s i ]| and let f min = min i f i . Without loss of generality, f min = f 0 . We first show that f min > 3. By Lemma 3, for any i ∈ {0, 1, 2}, |F ∩ (A i \ N [v 0 ])| ≥ x -5 -α and, for any i ∈ {0, 2}, |F ∩ (B i,0 \ N [v 0 ])| ≥ x -6 -(β + γ) and |F ∩ (B i,0 \ N [v 0 ])| ≥ x -6 -(β + γ). Therefore, 3x + 1 ≥ |F ∩ (A 0 ∪ A 0 ∪ A 1 ∪ A 2 ∪ B 0,0 ∪ B 2,0 ∪ B 0,0 ∪ B 2,0 )| ≥ 12 + 4(x -5 -α) + 4(x -6 -(β + γ)) -5|F ∩ N [s 0 ]| ≥ 8x -4(α + β + γ) -32 -5f min
Hence, 5f min ≥ 5x -4(α + β + γ) -33, and f min ≥ x -4 5 (α + β + γ) -7 > 3 by the above inequality.

Therefore, by definition of

f min , |F ∩ N [s i ]| ≥ 4 for any i ∈ {0, 1, 2}. By connectivity of the strategy, s i ∈ F ∩ N [s i ] for any i ∈ {0, 1, 2}. Hence, F must contain a subset of vertices inducing a subtree spanning S = N [v 0 ] ∪ {s 0 , s 1 , s 2 }.
Let T be an inclusion-minimal subset of F that induces a subtree spanning S.

By Claim 1, |T | ≥ α + β + 2γ + 15. Let T = T \ (N [v 0 ] ∪ 0≤i≤2 N [s i ]). Then, |T | ≥ α + β + 2γ -4.
Moreover, because of the symmetries, we may assume w.l.o.g., that T ⊆ 0≤i≤2 (A i ∪ B i ).

By Lemma 3 and because N (v 0 ) ⊆ F , for any 0

≤ i ≤ 2, |F ∩ (A i ∪ B i+1 mod 3 )| ≥ x + 8 -(α + 1) + 2x + 4 -(β + 2γ + 3) -12 = 3x -(α + β + 2γ) -4. Hence, |T |+|F ∩(A i ∪B i+1 mod 3 )| ≥ 3x-8. Let W i = F \(A i ∪B i+1 mod 3 ∪T ). Since |F | ≤ 3x + 1, it follows that |W i | ≤ 9.
Let f max = max i f i and assume w.l.o.g. that

f max = f 2 . Since 0≤i≤2 f i ≤ |F \ T |, we get that f 0 + f 1 ≤ 2 3 (5 + 3x -(α + β + 2γ) . To conclude, |F ∩B 0 | = |N (v 0 )|+f 0 +f 1 +|W 0 | ≤ 21+ 2
3 (5+3x-(α+β+2γ) . On the other hand, Lemma 3 implies that |F ∩B 0 | ≥ 2x+1-(β +2γ). Therefore,

Inria 22 + 2 3 (5 + 3x -(α + β + 2γ) > 2x + 1 -(β + 2γ
) and it follows 73 > 2α -β -2γ. This contradicts the inequalities.

Lemmas 4 and 5 are sufficient to prove Theorem 2. More precisely, it shows that there exist a family of graphs G and v 0 ∈ V (G) such that csn(G, v 0 ) ≥ sn(G, v 0 ) + 2. However, as shown in the next lemma, the family of graphs we described does not allow to increase more the lower bound on the cost of connectivity.

Lemma 6. csn(G, v 0 ) ≤ 3x + 2.
Proof. Consider the following strategy. At the first step, the observer marks the 12 neighbors of v 0 , all nodes of the paths A 0 , B 1 , C 1,1 and C 1,2 , the vertices w 1 , s 0 , s 1 and s 2 and finally Z = (3x -α -β -2γ -12)/3 one-degree neighbors of each s i . Note that Z ≥ 0 by Equation 3.

Then, the strategy goes on as follows. Let i ∈ {0, 1, 2}. When the surfer arrives at some node a i j (resp., a i j ), 1 ≤ j ≤ α, the observer marks the at most 3x unmarked neighbors of a i j and marks at least 2 unmarked neighbors of s i . When the surfer arrives at some node b i j (resp., b i j ), 1 ≤ j ≤ β, or at w i , the observer marks the at most 3x unmarked neighbors of this node and marks at least 1 unmarked neighbor of s i and at least 1 unmarked neighbor of s i+1 mod 3 . When the surfer arrives at some node c i, j (resp., c i, j ), 1 ≤ j ≤ γ, ∈ {i, i + 1 mod 3}, the observer marks the at most 3x unmarked neighbors of c i, j and marks at least 2 unmarked neighbors of s (if any) and, if all neighbors of s are already marked, the observer marks at least 2 unmarked neighbors of s k where {k} = {i, i + 1 mod 3} \ { }. Finally, when the surfer arrives at s i , the observer marks 3x + 2 unmarked neighbors of it.

To prove the validity of this strategy, it is sufficient to show that the surfer will loose for the following three different trajectories. This is sufficient, because the surfer is only able to win when moving from s 0 , s 1 or s 2 and because α < 2γ, i.e., the amount of steps it takes for the surfer to move from s i to s j , with j = i is bigger than the amount of steps it takes it to move from v 0 to s j . Meaning that, if the fugitive wins it wins the first time it moves out of one of these three vertices.

First, let us assume that the surfer goes from v 0 to s i through A i (i ∈ {0, 1, 2}). Clearly, at each step before reaching s i , all neighbors of the current position of the surfer are marked. Now, when the surfer arrives at s i , there are at least 2(α + 1) + Z neighbors of s i that are already marked. To show that the observer wins, it is sufficient to note that

|N (s i )| -(2(α + 1) + Z) = 4x -3 -2α -2 -(3x -α -β -2γ -12)/3 ≤ 3x -2α -5 + (α + β + 2γ + 12)/3 = 3x -1 + (β + 2γ -5α)/3 ≤ 3x + 2 because 2α > β + 2γ + 1.
Second, let us assume that the surfer goes from v 0 to s i through B i , w i and C i,i (i ∈ {0, 1, 2}). When the surfer arrives at s i , there are at least β +1+2γ +Z neighbors of s i that are already marked. To show that the observer wins, it is sufficient to note that

|N (s i )|-(β+1+2γ+Z) = 4x-3-β-1-2γ-(3x-α-β- 2γ -12)/3 ≤ 3x-β -4-2γ +(α+β +2γ +12)/3 ≤ 3x+(α-2β -4γ)/3 ≤ 3x+2 because α < β + γ + 1.
Finally, let us assume that the surfer goes from s i (all neighbors of which are already marked) to s i+1 mod 3 through C i,i , w i and C i,i+1 mod 3 (i ∈ {0, 1, 2}). When the surfer arrives at s i+1 mod 3 , there are at least 4γ + 2 + Z neighbors of s i+1 mod 3 that are already marked. To show that the observer wins, it is

sufficient to note that |N (s i+1 mod 3 )|-(4γ +2+Z) = 4x-3-4γ -2-(3x-α- β-2γ-12)/3 ≤ 3x-5γ-4+(α+β+2γ+12)/3 ≤ 3x-1+(α+β-10γ)/3 ≤ 3x+2 because β < α < 2γ + 1.
To conclude this section, we answer a question asked in [FGJM + 12] negatively. In this paper, it is shown that, for any graph G and

v 0 ∈ V (G), max |N [S]|-1 |S| ≤ sn(G, v 0 ) ≤ csn(G, v 0 )
where the maximum is taken over every subset S ⊆ V (G) inducing a connected subgraph with v 0 ∈ S [FGJM + 12]. Moreover, both previous inequalities turn into an equality in case of trees. The authors of [FGJM + 12] ask whether the first inequality may be strict.

First, let us notice that an equality might give new way to attack the question of the cost of the connectivity. However, such an equality is unlikely to hold since it would imply that the problem of computing the surveillance number of a graph is in co-NP while this problem is known to be PSPACE-complete in DAGs. We actually show that there are graphs where the inequality is strict.

Let us build a graph as follows. Starting from the vertex set V = {a, b, c, ab, ac, bc, s} and edge set E = {(s, a), (s, b), (s, c), (a, ab), (a, ac), (b, ab), (b, bc), (c, ac), (c, bc)}. Then, we add 11k-21-2x 6 leaves to each vertex ab, ac and bc, moreover, add 3 leaves to each vertex a, b and c, and, finally, add x leaves to s. A scheme of this family can be found in Figure 2. We moreover assume that k -5 ≡ 0 (mod 2), k -x -3 ≡ 0 (mod 3), 11k -21 -2x ≡ 0 (mod 6), x ≤ k -36 and k ≥ 34. For instance, k = 105 and x = 42 are possible.

Let G be the graph obtained by the above construction and where parameters satisfy the above constraints.

Theorem 7. sn(G, s) = k and max S⊆V (G) { |N [S]|-1 |S| } < k.
Proof. Troughout this proof, let M ⊆ V denote the set of (currently) marked vertices in G.

Inria

We show a strategy for the surfer that wins against an observer that can mark at most k -1 vertices per turn. Let

S a = (N [a] ∪ N [ab] ∪ N [ac]) \ {s, a, b, c}, S b = (N [b] ∪ N [ab] ∪ N [bc]) \ {s, a, b, c}, S c = (N [c] ∪ N [bc] ∪ N [ac]) \ {s, a, b, c}.
In the first step and after the observer has used its marks, the surfer chooses to move to i where i = arg min i={a,b,c} |S i ∩ M |. Since the observer must mark the vertices in N (s) (including a, b, c) we have that

|S i ∩ M | ≤ 2 3 (k -1 -x - 3).
Without loss of generality assume that i = a. In the second step, all neighbors of a must have been marked, otherwise the surfer wins by moving to an unmarked leaf of a. Let S ab = N [ab] \ {a, b, ab} and S ac = N [ac] \ {a, c, ac}, therefore, after all marks are spent in the second step, min j={ab,ac}

|S j ∩ M | ≤ k-1-5+ 2 3 (k-1-x-3) 2
. The surfer then chooses to move to arg min i={ab,ac} |S i ∩M |, w.l.o.g. assume that it is the vertex ab. In the third step, the observer might use all its available marks onto the leaves of ab, hence, after spending all the marks,

|S ab ∩ M | ≤ k -1 + k-1-5+ 2 3 (k-1-x-3) 2 = 11k-32-2x 6
which is less than |S ab |, hence there is an unmarked leaf of ab that the surfer can reach.

We consider now a winning strategy for the observer that marks k vertices per step. At the first step, the observer marks all vertices in N [s], with the remaining marks, k -x -3, being spread evenly among vertices in the sets N [ab] \ {a, b, ab}, N [ac] \ {a, c, ac} and N [bc] \ {b, c, bc}. Hence, there are at least k-x-3 3 = k-x-3 3 vertices marked in each of those sets. Without loss of generality assume that the surfer moves towards a. Then, the observer marks the vertices in N (a) and, with the remainning marks, proceeds to distribute them evenly among the vertices of the sets N (ab) and N (ac). When the surfer is about to move there are at least k-5

2 + k-x-3 3 = k-5 2 + k-x-3
3 vertices in (N (ab) \ {a, b}) ∩ M and in (N (ac) \ {a, c}) ∩ M . Without loss of generality assume that the surfer moves towards ab. Then the observer uses all its available marks on the unmarked vertices in N (ab) \ {a, b}. Therefore, after all marks are spent, there are k + k-5 2 + x-3 3 marked vertices in N (ab) \ {a, b}. It remains to show that k

+ k-5 2 + x-3 3 ≥ 11k-21-2x 6 . k + k -5 2 + x -3 3 ≥ 6k 6 + 3k -15 6 + 2x -6 6 -2 = 9k -21 + 2x 6 -2 9k -21 + 2x 6 -2 = 9k -33 + 4x -2x 6 ≥ 11k -21 -2x 6
Now we show that for all connected sets S such that s ∈ S we have that

|N [S]-1| |S| < k.
Claim 2. For all connected sets S such that s ∈ S, then

|N [S]-1| |S| ≤ k -1.
Proof. First we prove that if S contains a vertex v ∈ V with degree 1, then

|N [S]-1| |S| ≤ |N [S\{v}]-1|
|S\{v}| . Since S contains s and induces a connected subgraph, then

N (v) ⊂ S because |N (v)| = 1. Thus N [S \ {v}] contains v and so N [S \ {v}] = N [S].
In the rest of the proof, we consider sets S that do not contain a node with degree 1. Let L ab = N (ab)\{a, b}, L ac = N (ac)\{a, c}, and L bc = N (bc)\{b, c}. By the previous assumption, if a node v ∈ L ab is such that v ∈ N [S], then all nodes in L ab are in N [S]. By symmetry, we have the similar property for L ac and L bc . Note that (N (s) \ {a, b, c}) ⊂ N [S] because s ∈ S by definition.

We have four different cases:

• Consider S such that N [S] ∩ (L ab ∪ L ac ∪ L bc ) = ∅. We get that |S| ≥ 1 and N [S] ≤ x + 16. Thus |N [S]-1| |S| ≤ x + 15 ≤ k -1 because x ≤ k -36. • Consider S such that N [S] ∩ (L ac ∪ L bc ) = ∅ and L ab ⊂ N [S]. We get that |S| ≥ 3 and N [S] ≤ x + 16 + 11k-21-2x 6 . Thus |N [S]-1| |S| ≤ 11k+4x+69 18 ≤ k -1 because x ≤ k -36 and k ≥ 34. The case N [S] ∩ (L ab ∪ L bc ) = ∅ and L ac ⊂ N [S] is similar and the case N [S] ∩ (L ab ∪ L ac ) = ∅ and L bc ⊂ N [S] is also similar. • Consider S such that N [S] ∩ L bc = ∅ and L ab ∪ L ac ⊂ N [S]. We get that |S| ≥ 4 and N [S] ≤ x + 16 + 11k-21-2x 3 . Thus |N [S]-1| |S| ≤ 11k+x+24 12 ≤ k -1 because x ≤ k -36 and k ≥ 34. The case N [S] ∩ L ac ) = ∅ and L ab ∪ L bc ⊂ N [S] is similar and the case N [S] ∩ L ab ) = ∅ and L ac ∪ L bc ⊂ N [S] is also similar. • Consider S such that L ab ∪ L ac ∪ L bc ⊂ N [S]. We get that |S| ≥ 6 and N [S] ≤ x + 16 + 11k-21-2x 2 . Thus |N [S]-1| |S| ≤ 11k+9 12 ≤ k -1 because k ≥ 34.
Claim 2 concludes the proof of Theorem 7 because we have proved that sn(G, s) = k.

Online Surveillance Number

In this section, we study the online variant of the surveillance game motivated by the web-page prefetching problem where the observer (the web-browser) discovers new nodes through hyperlinks in already marked nodes. In this variant, the observer does not know a priori the graph in which it is playing. That is, initially, the observer only knows v 0 , its degree and the identifiers of its neighbors. Then, when a new node is marked, the observer discovers all its neighbors that are not yet marked. Note that the degree of a node is not known before it is marked.

Another property of an online strategy that must be defined concerns the moment when the observer discovers the unmarked neighbors of a node that it has decided to mark. There are two natural models. Assume that the set M of nodes have been marked and this is the turn of the observer, and let N (M ) be the set of nodes with a neighbor in M . Either it first chooses the k nodes that will be marked among the set N (M ) \ M of the unmarked neighbors of the nodes that were already marked and then the observer marks each of these k nodes and discover their unknown neighbors simultaneously. Or, the observer first chooses one node x in N (M ) \ M , marks it and discovers its unmarked neighbors, then it chooses a new node to be marked in N (M ∪ {x}) \ (M ∪ {x}) and so on until the observer finishes its turn after marking k nodes. We choose to consider the second model because it is less restricted, i.e., the observer has Inria more power, and, even in this case, our result is pessimistic since we show that the basic strategy is the best one with respect to the competitive ratio.

Formal definition of online strategy. Now we are ready to formally define an online strategy. Let k ≥ 1, let G = (V, E) be a graph, v 0 ∈ V , and let G be the set of subgraphs of G.

Given M ⊆ V be a subset of nodes inducing a connected subgraph containing v 0 in G. Let G M ∈ G be the subgraph of G known by the observer when M is the set of marked nodes. That is,

G M = (M ∪ N (M ), E M ) where E M = {(u, v) ∈ E | u ∈ M }. For any u, v ∈ N (M ) \ M , let us set u ∼ M v if and only if N (u) ∩ M = N (v) ∩ M . Let χ M
be the set of equivalent classes, called modules, of N (M ) \ M with respect to ∼ M . The intuition is that two nodes in the same module of χ M are known by the observer but cannot be distinguished. For instance, χ {v0} = {N (v 0 )} because initially all neighbors of v 0 look the same to the observer.

A k-online strategy for the observer starting from v 0 is a function σ :

G × V × 2 V × {1, • • • , k} → 2 V such
that, for any subset M ⊆ V of nodes inducing a connected subgraph containing v 0 in G, for any v ∈ M , and for any 1

≤ i ≤ k, then σ(G M , v, M, i) ∈ χ M .
This means that, if M is the set of nodes already marked and thus the observer only knows the subgraph G M , if v is the position of the surfer and it remains k -i + 1 nodes to be marked by the observer before the surfer moves, then the observer will mark one node in σ(G M , v, M, i).

More precisely, we say that the observer follows the k-online strategy σ if the game proceeds as follows. Let M = M 0 be the set of marked nodes just after the surfer has moved to v ∈ M . Initially, M 0 = {v 0 } and v = v 0 . Then, the strategy proceeds sequentially in k steps for i = 1 to k. First, the observer marks an arbitrary node x 1 ∈ σ(G M 0 , v, M 0 , 1). Let M 1 = M 0 ∪ {x 1 }. Sequentially, after having marked 1 < i < k nodes at this turn, the observer marks one arbitrary node x i+1 ∈ σ(G M i , v, M i , i + 1) and M i+1 = M i ∪ {x i+1 }. When the observer has marked k nodes, that is after choosing

x k ∈ σ(G M k-1 , v, M k-1 , k), it
is the turn of the surfer, when it may move to a node adjacent to its current position and then a new turn for the observer starts. Note that because we are interested in the worst case for the observer, each marked node

x i ∈ σ(G M i-1 , v, M i-1 , i) is chosen by an adversary.
The online surveillance number of a graph G with initial node v 0 , denoted by on(G, v 0 ), is the smallest k such that there exists a winning k-online strategy starting from v 0 . In other words, there is a winning k-online strategy σ starting from v 0 such that an observer following σ wins whatever be the trajectory of the surfer and the choices done by the adversary at each step. Note that, since we consider the worst scenario for the observer, we may assume that the surfer has full knowledge of G. Theorem 8. There exists a infinite family of rooted trees such that, for any T with root v 0 ∈ V (T ) in this family, sn(T, v 0 ) = 2 and on(T, v 0 ) = Ω(∆) where ∆ is the maximum degree of T .

Proof. We first define the family (T k ) k≥1 of rooted trees as follows.

Let k ≥ 4 be a power of two and let i = 2 k and d = 2 k k . Let us consider a path P = {v 0 , v 1 , . . . , v i-1 } with i nodes Let B be a complete binary tree of height h = 3k + 1 and rooted at some vertex v i , i.e., B The tree T k is obtained from P, B and Q by adding an edge between v i-1 and v i , an edge between w 0 and w 1 . Finally, for any 1 ≤ j ≤ k, let us add an independent set, S j , with d vertices and an edge between each vertex of S j and w j (i.e., each node in S j is a leaf in the resulting tree T k ). T k is then rooted in v 0 .

+ h = 3k + 1 d = 2 k k i = 2 k S1 S2 Sk d = 2 k k d = 2 k k w2
Let Q + denote the union of vertices of Q and k j=1 S j . The maximum degree ∆ of T k is reached by any node w j , 1 ≤ j < k, and ∆ = d + 2 = 2 k k + 2.

We first show that sn(T k , v 0 ) = 2. Clearly, sn(T k , v 0 ) > 1. Let us consider the following (offline) strategy for the observer.

At each turn j ≤ i, the surfer marks the vertex v j and one unmarked vertex of Q + that is closest to the surfer. Note that the observer is allowed to mark nodes in Q + because in an offline strategy, the observer knows the whole tree. Just after turn i, the surfer must occupy a node of P ∪{v i }. Moreover, it cannot have reached an unmarked vertex so far since all nodes of P ∪ {v i } have been marked before the surfer can access them.

For each turn j > i and while the surfer does not occupy a node in Q + ∪{w 0 }, the observer marks the neighbors of the current position of the surfer if they are not already marked. While the surfer remains on the nodes of B or P , this strategy clearly requires to mark at most 2 nodes per turn since B is a binary tree.

Finally, if the surfer occupies a node in Q + ∪ {w 0 }, the observer marks two unmarked nodes of Q + that are closest to the surfer. It only remains to prove that the surfer cannot reach an unmarked node in Q + . When the surfer reaches w 0 , this node must be marked by the previous strategy. Moreover, by the strategy of the first i turns, the i nodes of Q + that are closest to w 0 have been marked. Hence, for any 1 ≤ j ≤ k, when the surfer reaches w j , at least the i+2j

Inria nodes of Q + that are closest to w 0 are marked. Since | 1≤p≤j N [w p ] ∩ + | ≤ j(d + 1) + 1 and because i = dk, get that i + 2j = dk + 2j ≥ dj + j + 1 ≥ | 1≤p≤j N [w p ] ∩ Q + |
and therefore, the surfer never reaches a node with an unmarked neighbor.

Hence, sn(T k , v 0 ) = 2. Now it remains to show that on(T k , v 0 ) = Ω(∆). Let γ be any online strategy for T k and marking at most d 4 = 2 k-2 k nodes per turn. We show that γ fails.

For this purpose, we model the fact that the observer does not know the graph by "building" the tree during the game. More precisely, each time the observer marks a node v, then the adversary may add new nodes adjacent to v or decide that v is a leaf. Of course, the adversary must satisfy the constraint that eventually the graph is T k . Initially, the observer only knows v 0 that has one neighbor v 1 . Now, for any 1 ≤ j < i, when the observer marks the node v j of P , then the adversary "adds" a new node v j+1 adjacent to v j , i.e., the observer discovers its single unmarked neighbor v j+1 . Now, let v be any node of B. Recall that h is the height of B. When the observer marks v, there are three cases to be considered: if v is at distance at most h -1 from v i , then the adversary adds two new nodes adjacent to v; if v is at distance h from v i and not all nodes of B have been marked then the adversary decides that v is a leaf; finally, if all nodes of B have been marked (v is the last marked node of B, i.e., B is a complete binary tree of height h), the adversary decides that v = w 0 and add one new neighbor w 1 adjacent to it. Note that we can ensure that the last node of B to be marked is at distance h of v i by connectivity of any online strategy. Now, let consider the following execution of the game. During the first i steps, the surfer goes from v 0 to v i . Just after the surfer arrives in v i , the observer has marked at most (di)/4 nodes and all nodes of P ∪ {v i } must be marked since otherwise the surfer would have won. Therefore, at most i(d/4 -1) + 1 = 2 2k-2 /k -2 k + 1 nodes of B are marked when it is the turn of the surfer at v i . Since B has 2 h+1 -1 = 2 3k+2 -1 nodes, at least one node of B is not marked.

From v i , the surfer always goes toward w 0 . Note that the observer may guess this strategy but it does not know where is w 0 while all nodes of B have not been marked.

Then let 0 ≤ t ≤ h and let v t ∈ V (B) be the position of the surfer at step i + t and B t the subtree of B rooted at v t . Note that, at step i, v 0 = v i and B 0 = B. Let B t l and B t r be the subtrees of B rooted at the children of v t . W.l.o.g., let us assume that the number of marked nodes in B t l is at most the number of marked nodes in B t r , when it is the turn of the surfer standing at v t . Then, the surfer moves to the root of B t l . That is, v t+1 is the child of v t whose subtree contains the minimum number of marked nodes. Let m t be the number of marks in the subtree of B rooted at v t when it is the turn of the surfer at v t . Since, at beginning of step i there are at most 2 2k-2 /k -2 k +1 nodes of B that are marked and k ≥ 4, m 0 ≤ 2 2k-2 /k -2 k +1 ≤ 2 2k-2 /k. Note that, for any t > 0, m t ≤ (m t-1 -1 + d 4 )/2 ≤ (m t-1 + d 4 )/2. Simply expanding this expression we get that, for any t > 0,

m t ≤ m 0 2 t + 2 k k t+2 j=3 2 -j ≤ 2 2k-(t+2) k + 2 k k t+2 j=3 2 .
for any t ≥ 2k:

m t ≤ 1 k + 2 k k t+2 j=3 2 -j ≤ 2 k + 1 k .
In particular, at step i + 2k (when it is the turn of the surfer), the surfer is at v 2k which is at distance k + 1 from w 0 . Hence, |B 2k | ≥ 2 k+1 -1 and at most 2 k +1 k < 2 k+1 -1 of its nodes are marked. Hence, w 0 neither no nodes in Q + are marked.

From this step, the surfer directly goes to w k unless she meets an unmarked node, in which case, she goes to it and wins. When the surfer is at w k and it is her turn, the observer may have marked at most (2k+2)

d 4 ≤ kd 2 + d 2 ≤ 2 k-1 + 2 k-1
k nodes in Q + . Since |Q + | = (d + 1)k = 2 k + k and k ≥ 4, at least one neighbor of w k is not marked yet and the surfer wins.

A direct consequence of this theorem is the following result:

Corollary 1. No online winning strategy has better competitive ratio than the basic strategy up to a constant factor.

As mentioned in the introduction, any online strategy is connected and therefore, for any graph G and v 0 ∈ V (G), csn(G, v 0 ) ≤ on(G, v 0 ). Moreover, we recall that, for any tree T and for any v 0 ∈ V (T ), csn(T, v 0 ) = sn(T, v 0 ) [FGJM + 12]. Hence, the previous theorem shows that there might be an arbitrary gap between csn(G, v 0 ) and on(G, v 0 ).

Conclusion

Despite our results, the main question remains open. Can the difference or the ratio between the connected surveillance number of a graph and its surveillance number be bounded by some constant?

  are marked. Therefore, w.l.o.g., there are at most |M |+y(β+1)-12 2 nodes that are marked in (N [C 0,0 ]∪N [s 0 ])\N [w 0 ]. The surfer now goes from w 0 to s 0 . During these steps, at most (γ +1)(3x+y) new vertices are marked. Because S is a winning strategy, all nodes in (N [C 0,0 ] ∪ N [s 0 ]) \ N [w 0 ] must have been marked since otherwise the surfer would have won. Therefore, |M |+y(β+1)-12 2 + (γ + 1)(3x + y) ≥ |(N [C 0,0 ]∪N [s 0 ])\N [w 0 ]| = 3γx+4x-4. Hence, |M | ≥ 2x+4-y(β+2γ+3).

Lemma 4 .

 4 sn(G, v 0 ) = 3x.

Figure 2 :

 2 Figure 2: Scheme of the graph family described in the proof of Theorem 7.

Figure 3 :

 3 Figure 3: Tree T k described in the proof of Theorem 8.

RR n°8297