The radius capture number Tanja Dravec, Vesna Iršič Chenoweth, Andrej Taranenko Abstract In the classic cop and robber game, two players–the cop and the robber–take turns moving to a neighboring vertex or staying at their current position. The cop aims to capture the robber, while the robber tries to evade capture. A graph G G is called a cop-win graph if the cop can always capture the robber in a finite number of moves. In the cop and robber game with radius of capture k k , the cop wins if he can come within distance k k of the robber. The radius capture number rc ⁡ ( G ) {\rm rc}(G) of a graph G G is the smallest k k for which the cop has a winning strategy in this variant of the game. In this paper, we establish that rc ⁡ ( H ) ≤ rc ⁡ ( G ) {\rm rc}(H)\leq{\rm rc}(G) for any retract H H of G G . We derive sharp upper and lower bounds for the radius capture number in terms of the graph’s radius and girth, respectively. Additionally, we investigate the radius capture number in vertex-transitive graphs and identify several families ℱ \cal{F} of vertex-transitive graphs with rc ⁡ ( G ) = rad ⁡ ( G ) − 1 {\rm rc}(G)=\rad(G)-1 for any G ∈ ℱ G\in\cal{F} . We further study the radius capture number in outerplanar graphs, Sierpiński graphs, harmonic even graphs, and graph products. Specifically, we show that for any outerplanar graph G G , rc ⁡ ( G ) {\rm rc}(G) depends on the size of its largest inner face. For harmonic even graphs and Sierpiński graphs S ⁡ ( n , 3 ) S(n,3) , we prove that rc ⁡ ( G ) = rad ⁡ ( G ) − 1 {\rm rc}(G)=\rad(G)-1 . Regarding graph products, we determine exact values of the radius capture number for strong and lexicographic products, showing that they depend on the radius capture numbers of their factors. Lastly, we establish both lower and upper bounds for the radius capture number of the Cartesian product of two graphs. 1 Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia 2 Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia 3 Faculty of Mathematics and Physics, University of Ljubljana, Slovenia Keywords : Cop and robber game, radius capture number, vertex-transitive graphs, outerplanar graphs, graph products AMS Subj. Class. (2020): 05C12, 05C57 1 Introduction The cop and robber game, introduced by Nowakowski and Winkler [ 18 ] and Quilliot [ 21 ] , was intensively studied by numerous authors [ 7 , 12 ] . The cop and robber game is a pursuit-evasion game played on the vertices of finite undirected graphs. First, the cop occupies his initial position, then the robber occupies another vertex. Then they (starting with the cop) alternately either move to an adjacent vertex or stay in the same vertex. Both players know the position of the opposing player. The aim of the cop is to capture the robber, i.e. to occupy the vertex that is occupied by the robber, while the robber wants to evade the cop. A graph G is a cop-win graph if the cop has a strategy to capture the robber after a finite number of moves regardless of the robber’s playing strategy. A corner of a graph G is a vertex u such that there exists v\in V(G) with N[u]\subseteq N[v] . A graph G is dismentlable if there exists a sequence of corners whose iterative deletion results in K_{1} . Cop-win graphs are exactly dismantlable graphs [ 18 , 21 ] . Since the introduction many variants of the cop and robber game were developed. The most natural one replaces a single cop with a set of cops. In this sense the cop number of a graph G , c(G) , was introduced by Aigner and Fromme [ 1 ] , as the minimum number of cops needed to capture the robber in G . The distance k cop and robber game was introduced by Bonato and Chiniforooshan [ 5 ] . In this game the cop wins if he is at distance at most k from the robber. The distance k cop number of a graph G , c_{k}(G) , is the minimum number of cops necessary to win at a given distance k . The game was further studied in [ 9 ] under a different name: the cop and robber game with radius of capture k . We will use this name and denote by {\cal{CWRC}}(k) the set of graphs in which cop has a winning strategy in the cop and robber game with radius of capture k regardless of how robber is playing. In [ 6 ] an O(n^{2s+3}) algorithm for testing weather c_{k}(G)\leq s is presented. Moreover, upper and lower bounds in terms of order are proved for c_{k}(G) . Chalopin et al. considered the cop and robber game with radius of capture 1 on bipartite graphs [ 9 ] . They characterized bipartite graphs in {\cal{CWRC}}(1) and explain that the characterization for general graphs seems to be quite challenging. Graphs in {\cal{CWRC}}(1) were studied also in [ 11 ] , where the cop and robber game with radius of capture 1 was considered on square-grids, k -chordal graphs and outerplanar graphs. In this paper we define the radius capture number of a graph G , \rc(G) , as the smallest k such that G\in{\cal{CWRC}}(k) , i.e. \rc(G)=\min{\{k\mid G\in{\cal{CWRC}}(k)\}} . Note, that we always consider the game with exactly one cop. Hence, if G is a cop-win graph, then \rc(G)=0 . If G is not connected, then G\notin{\cal{CWRC}}(k) for any k\in{\mathbb{N}}_{0} , i.e. robber has a winning strategy in the cop and robber game with radius of capture k . Namely, if cop in his first move selects a vertex in the component G_{1} of G , then robber selects a vertex in any component different from G_{1} and wins the game. For this reason if not explicitly stated we will always consider connected graphs. In Section 2 we start with basic definitions and present some preliminary results. We show that if G\in{\cal{CWRC}}(k) , then {H\in\cal{CWRC}}(k) holds for any retract H of G . In Section 3 we present tight upper and lower bounds for the radius capture number of an arbitrary graph. Section 4 is devoted to vertex-transitive graphs. We consider different families of vertex-transitive graphs and determine exact values of the radius capture number for all graphs in presented families. We prove that any generously-transitive graph G satisfies \rc(G)=\rad(G)-1 . Moreover, we show that distance-transitive graphs and generalized Johnson graphs are generously-transitive and thus we obtain the exact value of the radius capture number for any distance-transitive and any generalized Johnson graph. We also show that not all vertex-transitive graphs G satisfy \rc(G)=\rad(G)-1 . Finally, in Section 5 we investigate the radius capture number of outerplanar graphs, harmonic even graphs, Sierpiński graphs and graph products. We prove that for any outerplanar graph G , \rc(G) depends on the size of the largest inner face. We present both upper and lower bounds for the radius capture number of the Cartesian product of two graphs. Moreover, for the strong and lexicographic product we get exact values of the radius capture number which depend on the radius capture number of the factors. 2 Preliminaries Let G=(V,E) be a graph. The distance between two vertices u,v\in V(G) , d_{G}(u,v) , is the length of a shortest u,v -path in G . For C\subseteq V(G) and v\in V(G) , d_{G}(v,C)=\min{\{d_{G}(v,x)\mid x\in V(C)\}} . The open neighborhood of u\in V(G) , N_{G}(u) , is the set of neighbors of u and the closed neighborhood of u is the set N_{G}[u]=N_{G}(u)\cup\{u\} . For S\subseteq V(G) the closed neighborhood of S is the set N_{G}[S]=\bigcup_{u\in S}N_{G}[u] . When the graph G is clear from the context, we shall omit it in the notation. The subgraph of G induced by S is denoted by G[S] and for v\in V(G) we write G-\{v\} instead of G[V(G)\setminus\{v\}]. For a connected graph G and v\in V(G) the eccentricity of v , \ecc(v) , is the maximum distance between v and any other vertex u of G, i.e. \ecc(v)=\max{\{d(v,u)\mid u\in V(G)\}} . In a graph G , an antipode of a given vertex v is a vertex u with d(v,u)=\ecc(v) . The diameter of a graph G is defined as diam (G)=\max{\{\ecc(v)\mid v\in V(G)\}} and the radius of G is rad (G)=\min{\{\ecc(v)\mid v\in V(G)\}} . The girth of a graph G , g(G) , is the length of one of its (if any) shortest graph cycles. In this paper acyclic graphs are considered to have girth 0 . A homomorphism f from a graph G to a graph H is a function f:V(G)\to V(H) that maps edges to edges, i.e. if xy\in E(G) then f(x)f(y)\in E(H) . An induced subgraph H of G is a retract of G if there exists a homomorphism f:V(G)\to V(H) such that f(h)=h holds for any h\in V(H) . The map f is in this case called a retraction . It was proved in [ 3 ] that the cop number of a retract H of G never exceeds the cop number of G . We will use the same ideas to prove that if H is a retract of G then G\in{\cal{CWRC}}(k) implies that H\in{\cal{CWRC}}(k) . We will start by presenting some well-known properties of retracts. Remark 1 . Let H be an induced subgraph of a connected graph G and f:V(G)\to V(H) a retraction. Then d_{G}(x,y)\geq d_{H}(f(x),f(y)) for any x,y\in V(G) . Let H be a retract of G . Remark 1 implies that for any x,y\in V(H)\subseteq V(G) , d_{G}(x,y)\geq d_{H}(f(x),f(y))=d_{H}(x,y) . Hence d_{G}(x,y)=d_{H}(x,y) holds for all x,y\in V(H) and thus a retract H of a graph G is always isometric subgraph of G . Theorem 2 . Let H be a retract of a connected graph G and k an arbitrary non-negative integer. If G\in{\cal{CWRC}}(k) , then H\in{\cal{CWRC}}(k) . Proof. Let f:V(G)\to V(H) be a retraction and let G\in{\cal{CWRC}}(k) . Hence the cop has a winning strategy on G for the cop and robber game with radius of capture k . Consider two parallel cop and robber games with radius of capture k , one played on G and the other played on H . Since H is an induced subgraph of G , the game in H can be considered as being played on G . The cop on G plays by using his optimal strategy (he has a winning strategy on G since G\in{\cal{CWRC}}(k) ) and uses the following shadow strategy for playing on H . If in his i^{\text{th}} move the cop is in v when playing on G , then he will move to f(v) when playing on H and f(v) is then called the shadow of v . If on G cop moves from u to v , then on H he moves from f(u) to f(v) . Hence u=v or uv\in E(G) and since f is homomorphism, f(u)=f(v) or f(u)f(v)\in E(H) . Thus the move from f(u) to f(v) is a valid move for the cop on H . It remains to prove that the described cop’s strategy is a winning strategy for the cop and robber game with radius of capture k played on H . Suppose that cop in his i^{\text{th}} move, when playing on G , selects the vertex c_{i} . Then, by the above described strategy, he occupies c_{i}^{\prime}=f(c_{i}) in the game on H . Moreover, let r_{i}^{\prime} be the vertex occupied by the robber in his i^{\textrm{th}} move when he plays on H . Then the cop imagines that this was robbers move in G and follows his strategy on G . Since f is a homomorphism, Remark 1 implies that d_{H}(f(r_{i}^{\prime}),f(c_{i}))=d_{H}(r_{i}^{\prime},c_{i}^{\prime})\leq d_{G}(r_{i}^{\prime},c_{i}) . Since G\in{\cal{CWRC}}(k) , there exists i such that d_{G}(r_{i}^{\prime},c_{i})\leq k and thus d_{H}(r_{i}^{\prime},c_{i}^{\prime})\leq k which implies that H\in{\cal{CWRC}}(k) . ∎ In [ 9 ] authors characterized bipartite graphs that are in {\cal{CWRC}}(1) . The proof of that result could be simplified by using Theorem 2 . If G is a bipartite graph from {\cal{CWRC}}(1) , then the cop has a winning strategy in the cop and robber game with radius of capture 1 . Let v be the next-to-last position of the robber in the game played on G . The proof in [ 9 ] goes by induction and the main step of the proof is to see that G^{\prime}=G-\{v\} belongs to {\cal{CWRC}}(1) . Authors also note that G^{\prime} is retract of G and thus by Theorem 2 it directly follows that G^{\prime}\in{\cal{CWRC}}(1) . 3 Bounds and complexity In this section we prove a sharp upper and a lower bound for the radius capture number of an arbitrary connected graph G . Theorem 3 . If G is a connected graph, then \rc(G)\leq\rad(G)-1 . Proof. Let G be a connected graph and let k=\rad(G) . We will prove that G\in{\cal{CWRC}}(k-1) . Let v\in V(G) be a vertex with the smallest eccentricity, i.e. \ecc(v)=\rad(G) . The cop’s strategy is that he occupies v in his first move. Let u be the vertex occupied by the robber in his first move and let v^{\prime} be the neighbor of v on a shortest u,v -path. The cop then moves from v to v^{\prime} . Since d_{G}(v^{\prime},u)\leq k-1 the cop wins the cop and robber game with radius of capture k-1 and thus G\in{\cal{CWRC}}(k-1) . ∎ The bound in Theorem 3 is sharp. For example, if n is even, then \rc(C_{n})=\frac{n}{2}-1=\rad(C_{n})-1 . There are also many other graphs that attain this bound. We will prove in the next section that Johnson and Kneser graphs attain this bound. If for any two vertices x,y\in V(G) with d(x,y)=\rad{(G)} it holds that for any x^{\prime}\in N[x] there exists y^{\prime}\in N[y] with d(x^{\prime},y^{\prime})=\rad{(G)} , then \rc(G)=\rad(G)-1 . Thus we can easily get a sufficient condition for graphs G with rc(G)=\rad{(G)}-1 . But it is not clear if this condition is also necessary. Problem 4 . Characterize connected graphs G with \rc(G)=\rad(G)-1 . We mention the following corollary of the upper bound from Theorem 3 and an algorithm given in [ 6 ] . Corollary 5 . Determining \rc(G) for a graph G on n vertices can be done in time O(n^{6}) . Proof. By definition, the smallest such r for which c_{k}(G)\leq 1 equals \rc(G) . Using the polynomial algorithm from [ 6 ] which checks if c_{k}(G)\leq 1 in time O(n^{5}) , combined with the upper bound from Theorem 3 the following simple algorithm determines \rc(G) in time O(n^{6}) . For k=0,1,\ldots,\rad(G)-1 , check if c_{k}(G)\leq 1 . If yes, return k ; otherwise proceed to the next k . Thus the algorithm from [ 6 ] implies that determining \rc(G) can be done in polynomial time as asserted. ∎ Theorem 6 . If G is a connected graph, then \rc(G)\geq\left\lfloor\frac{g(G)}{2}\right\rfloor-1 . Proof. Let C:x_{1},x_{2},\ldots,x_{k},x_{1} be a shortest cycle of G (of length k ) and let c_{1}=v be the vertex occupied by the cop in his first move. The strategy of robber is to first select a vertex r_{1} on C which is at distance at least \left\lfloor\frac{k}{2}\right\rfloor from c_{1} and always only move on C in such a way that after each of the robber’s moves it holds true that d_{G}(c_{i},r_{i})\geq\left\lfloor\frac{k}{2}\right\rfloor , where c_{i} and r_{i} denote the vertices occupied by the cop and the robber in the i^{\text{th}} move, respectively. In the rest of the proof we show that for any i , such a vertex r_{i} for the robber exists. The proof goes by induction on i . Since k=g(G) , there exists j\in[k] such that d_{G}(c_{1},x_{j})\geq\left\lfloor\frac{k}{2}\right\rfloor and hence r_{1}=x_{j} has the desired property. Now, let c_{i} be the vertex occupied by the cop in his i^{\text{th}} move and let r_{i-1}=x_{j^{\prime}} for some j^{\prime}\in[k] (remember, that the robber’s strategy is to only move on C ). By the induction assumption d_{G}(c_{i-1},r_{i-1})\geq\lfloor\frac{k}{2}\rfloor . If d_{G}(c_{i},r_{i-1})\geq\lfloor\frac{k}{2}\rfloor , then let r_{i}=r_{i-1} . Otherwise, d_{G}(c_{i},r_{i-1})=\lfloor\frac{k}{2}\rfloor-1 . If c_{i} is on the cycle C there clearly exists x_{j^{\prime\prime}}\in N(x_{j^{\prime}})\cap V(C) such that d_{G}(c_{i},x_{j^{\prime\prime}})=\lfloor\frac{k}{2}\rfloor , thus r_{i}=x_{j^{\prime\prime}} and this case is done. If c_{i} is not a vertex of the cycle C and x_{j^{\prime\prime}}\in N(x_{j^{\prime}})\cap V(C) such that d_{G}(c_{i},x_{j^{\prime\prime}})=\lfloor\frac{k}{2}\rfloor-1 , then the vertices c_{i},x_{j^{\prime}} and x_{j^{\prime\prime}} lie on an induced cycle of length at most \lfloor\frac{k}{2}\rfloor-1+\lfloor\frac{k}{2}\rfloor-1+1=2\lfloor\frac{k}{2}\rfloor-1\leq k-1 , a contradiction with the fact that k is the length of a shortest cycle. Thus, the robber can move to any of the two neighbors of x_{j^{\prime}} on the cycle C . This completes the proof. ∎ The bound from Theorem 6 is sharp. For any n\geq 4 , \rc(C_{n})=\lfloor\frac{n}{2}\rfloor-1=\lfloor\frac{g(G)}{2}\rfloor-1 . We will prove in Section 5.1 that outerplanar graphs in which all inner faces are of the same length also attain this bound. 4 Vertex-transitive graphs In this section we determine the value for the radius capture number for different classes of vertex-transitive graphs. All presented families of graphs in this section achieve the upper bound from Theorem 3 . However, this is not true for all vertex-transitive graphs, as we show towards the end of this section. A graph G is vertex-transitive if for any u,v\in V(G) there exists an automorphism that maps u to v . A graph G is generously-transitive if for any u,v\in V(G) there exists an automorphism \varphi with \varphi(v)=u and \varphi(u)=v . In the next result we prove that all generously-transitive graphs achieve the bound from Theorem 3 . Theorem 7 . If G is generously-transitive, then \rc(G)=\rad(G)-1 . Proof. Let k=\rad(G) . By Theorem 3 , \rc(G)\leq k-1 . To prove the reversed inequality we need a strategy for the robber that guarantees that at each time of the game the distance between the cop and the robber is at least k-1 . Let c_{1} be the vertex chosen by the cop in his first move. Since k=\rad(G) , there exists a vertex x with d(c_{1},x)\geq k . Let r_{1}=x be the vertex chosen by the robber in his first move. Now, we will prove inductively that after each robber’s move it holds true that d(c_{i},r_{i})\geq k , where c_{i},r_{i} denote the vertices occupied by the cop and the robber in their i^{\text{th}} -move, respectively. Suppose that d(c_{i},r_{i})\geq k and let c_{i+1} be the vertex occupied by the cop in his next move. If d(c_{i+1},r_{i})\geq k , then robber has a strategy to stay in r_{i} , i.e. r_{i+1}=r_{i} . Otherwise, it holds that d(c_{i+1},r_{i})=k-1 . By the assumption, there exists an automorphism \varphi:V(G)\to V(G) with the property \varphi(c_{i+1})=r_{i} and \varphi(r_{i})=c_{i+1} . Since c_{i+1} has a neighbor c_{i} that is at distance k from r_{i} , it holds that f(c_{i+1})=r_{i} has a neighbor x=f(c_{i}) that is at distance k from f(r_{i})=c_{i+1} . Thus let r_{i+1}=x , which implies that d(c_{i+1},r_{i+1})=k . Therefore after each robber’s move the distance between both players is at least k and hence \rc(G)\geq k-1 . ∎ Cayley graphs of Abelian groups have generously transitive automorphism groups [ 14 ] . Thus we get the following. Corollary 8 . If G is a Cayley graph of an Abelian group, then \rc(G)=\rad(G)-1 . A graph G is distance-transitive if for any vertices u,v,x,y\in V(G) for which d(u,v)=d(x,y) , there is an automorphism of G that maps u to x and v to y [ 4 ] . Lemma 9 . If G is a distance-transitive graph, then it is generously-transitive. Proof. Let G be a distance-transitive graph and let u,v\in V(G) be arbitrary. Denote by i=d(u,v) . Since G is distance-transitive, for any two pairs of vertices at distance i , also for (u,v) and (v,u) , there exist an automorphism that maps u to v and v to u . ∎ Theorem 7 and Lemma 9 imply the following result. Corollary 10 . If G is a distance-transitive graph, then \rc(G)=\rad(G)-1 . Let n>k>i be non-negative integers. The generalized Johnson graph, J(n,k,i) is the graph whose vertices are the k -subsets of an n -set, where vertices A and B are adjacent whenever |A\cap B|=i . We will consider two special cases of generalized Johnson graphs, the Johnson graphs and Kneser graphs. Johnson graphs are generalized Johnson graphs with i=k-1 , i.e. two k -subsets A,B of an n -set X are adjacent if and only if |A\cap B|=k-1 . Johnson graphs are denoted by J(n,k)=J(n,k,k-1) and satisfy \rad(J(n,k))=k [ 16 ] . Moreover, graph J(n,k) is isomorphic to J(n,n-k) and hence we may always assume that k\leq\frac{n}{2} . Since Johnson graphs are distance-transitive [ 17 ] , we get the following. Corollary 11 . Let n be a positive integer and 1\leq k\leq\frac{n}{2} . Then \rc(J(n,k))=k-1=\rad(J(n,k))-1. There are many other well-known vertex-transitive graph classes that are contained in the class of distance-transitive graphs, such as Grassmann graphs, odd graphs, hypercubes, Hamming graphs, triangular graphs, complete k -partite graphs, etc. Corollary 10 implies that for any such graph G it holds that \rc(G)=\rad(G)-1 . Kneser graphs are generalized Johnson graphs with i=0 . Hence vertices of Kneser graphs K(n,k)=J(n,k,0) are k -subsets of the n -set X and two vertices A,B\in V(K(n,r)) are adjacent if and only if A\cap B=\emptyset . Some Kneser graphs are distance-transitive, for example odd graphs. However, this is not true for all Kneser graphs and thus generalized Johnson graphs are not distance-transitive in general. Next, we prove that the bound from Theorem 3 is also tight for all generalized Johnson graphs. Theorem 12 . If G is a generalized Johnson graph, then \rc(G)=\rad(G)-1 . Proof. Let n>k>i be non-negative integers. By Theorem 3 , \rc(G)\leq\rad(J(n,k,i))-1 . Now, let A and B be arbitrary vertices of J(n,k,i) and let |A\cap B|=\ell for some \ell\in\{0,1,\ldots,k-1\} . Let A=\{a_{1},\ldots,a_{\ell},a_{\ell+1},\ldots,a_{k}\} and B=\{a_{1},\ldots,a_{\ell},b_{\ell+1},\ldots,b_{k}\} . Define f:\{1,\ldots,n\}\to\{1,\ldots,n\} , f(x)=\begin{cases}b_{i},&\text{if }x=a_{i}\text{ for some }i\in\{\ell+1,\ldots,k\},\\ a_{i},&\text{if }x=b_{i}\text{ for some }i\in\{\ell+1,\ldots,k\},\\ x,&\text{ otherwise.}\end{cases} Moreover, let F:V(J(n,k,i))\to V(J(n,k,i)) , F(X)=\{f(x)\mid x\in X\} . Clearly f is a bijection. Since |X\cap Y|=|F(X)\cap F(Y)| holds for any X,Y\in V(J(n,k,i)) , F maps edges to edges and non-edges to non-edges and thus F is an automorphism. Since F(A)=B and F(B)=A , we have proved that for arbitrary A,B\in V(J(n,k,i)) , there exists an automorphism F that maps A to B and B to A . Therefore J(n,k,i) is a generously-transitive and thus Theorem 7 implies that \rc(J(n,k,i))=\rad(J(n,k,i))-1 . ∎ There also exist vertex-transitive graphs G with \rc(G)\leq\rad(G)-2 . To see this we need the following lemma. Lemma 13 . Let G be a connected graph and i\leq\rad(G) an non-negative integer. If for any two vertices x,y\in V(G) such that d(x,y)=i there exists y^{\prime}\in N(y) with d(x,y^{\prime})=i+1 , then \rc(G)\geq i . Proof. Let i be a non-negative integer such that for any two vertices x,y\in V(G) such that d(x,y)=i there exists y^{\prime}\in N(y) with d(x,y^{\prime})=i+1 . We present a strategy for the robber to win the cop and robber game with radius of capture i-1 . Regardless of the cop’s first move, the robber selects the antipodal vertex of the vertex chosen by the cop. If in some step of the game, after the cop’s move, the distance between both players is i , then robber in his next move selects its neighbor that is at distance i+1 from the cop, since such a vertex exists by assumption. Hence, the cop cannot capture the robber in the cop and robber game with radius of capture i-1 and therefore \rc(G)\geq i . ∎ Figure 1 shows a graph G called CubicVT[24,6] in the census of small connected cubic vertex-transitive graphs provided by Potočnik et. al. [ 20 ] . This graph has order 24 and radius 5. Moreover, for every vertex v\in V(G) there exists exactly one vertex u\in V(G) with d(u,v)=5 . We first show that G\in{\cal{CWRC}}(3) . Let c_{1} be the first cop’s move. If the robber does not want to lose the game in the cop’s next move, then the robber in his first move selects the vertex r_{1} with d(c_{1},r_{1})=5 . Next, in his second move the cop selects the vertex c_{2} (see Figure 1 ). Since d(c_{2},r)\leq 4 holds for any r\in N[r_{1}] , the robber will, regardless of his next move, lose the cop and robber game with radius of capture 3 in the cop’s next move. Thus, G\in{\cal{CWRC}}(3) and consequently \rc(G)\leq 3 . Since every vertex x\in V(G) that is at distance 3 from c_{1} has a neighbor x^{\prime} with d(c_{1},x^{\prime})=4 , using that G is vertex-transitive Lemma 13 implies that \rc(G)\geq 3 . Hence, the graph G depicted in Figure 1 is an example of a vertex-transitive graph with \rc(G)=\rad(G)-2 . Note, this graph is also a Cayley graph, thus not all Cayley graphs achieve the bound from Theorem 3 . c_{1} c_{2} r_{1} Figure 1: The graph CubicVT[24,6] from the census of small connected cubic vertex-transitive graphs [ 20 ] . We have computed the radius capture number of all graphs available in the census of small connected cubic vertex-transitive graphs [ 20 ] and vertex-transitive graphs G for which the difference \rad(G)-\rc(G) is greater than 2 also exist. For example, the graph CubicVTgraph[56,12] from the census was the highest order graph for which the radius capture number is equal to the half of the radius, namley \rad(\text{\emph{CubicVTgraph[56,12]}})=6 and \rc(\text{\emph{CubicVTgraph[56,12]}})=3 . On the other hand, no tested graph had the radius capture number smaller than one half of the radius, moreover we found seven graphs from the census that achieve this lower bound. Hence, we propose the following question. Question 14 . If G is a vertex-transitive graph, can the lower bound from Theorem 6 be improved? Can it be proven that \rc(G)\geq\frac{\rad(G)}{2} ? We finish the section with the following question which is a special case of Problem 4 . Question 15 . Which vertex-transitive graphs G have the radius capture number equal to \rad(G)-1 ? 5 Other graph classes 5.1 Outerplanar graphs An outerplanar graph is a planar graph that can be embedded in the plane so that all its vertices lie on the same face, called the outer face. Note that outerplanar graphs G with \rc(G)\leq 1 were characterized in [ 11 ] as outerplanar graphs having all inner faces of length at most 5. In the next theorem we generalize this result and present explicit formula for \rc(G) , where G is an arbitrary outerplanar graph. Theorem 16 . Let G be an outerplanar graph embedded in the plane and C a longest inner face of G . Then \rc(G)=\left\lfloor\frac{|V(C)|}{2}\right\rfloor-1 . Proof. We first present a robber’s strategy which guaranties that at every step of the game the distance between the cop and the robber is at least \left\lfloor\frac{|V(C)|}{2}\right\rfloor-1 . Define a mapping \sigma:V(G)\to 2^{V(C)} such that \sigma maps v\in V(G) to the set \{x\in V(C)\mid d(v,C)=d(v,x)\} . We call \sigma(v) the set of shadows of v . The cop will play the game optimally on G and the robber will imagine the cop’s moves on C and respond by only playing on C . If the cop moves to c_{i}\in V(G) , then the robber imagines that the cop is on a vertex c_{i}^{\prime}\in\sigma(c_{i}) on C and the robber’s strategy is to move to an antipodal vertex r_{i}\in V(C) of c_{i}^{\prime} on C . Since C\subseteq G , the cop continues playing on G by responding to the robber’s move r_{i} . Note, that by using this strategy, after each robber’s move the distance between the cop and the robber is at least \left\lfloor\frac{|V(C)|}{2}\right\rfloor . We use induction on the number of moves to show that the robber can always move as described by the above strategy. First, since G is outerplanar we note that for any v\in V(G) , it holds true that |\sigma(v)|\leq 2 and G[\sigma(v)] is either isomorphic to K_{1} or K_{2} . Hence, the set of antipodal vertices of all vertices in \sigma(v) is of cardinality at most 2, if C is of even length, and of cardinality at most 3, if C is of odd length. Denote by A(\sigma(v)) the set of antipodal vertices (with respect to C ) of all vertices in \sigma(v) . Since G is outerplanar we can easily deduce the following remark. Remark 17 . If vu\in E(G) , then for any x\in A(\sigma(v)) there exists y\in A(\sigma(u)) such that y\in N[x] . If c_{1} is the vertex occupied by the cop in his first move and the robber responds by choosing an antipodal vertex of a vertex from \sigma(c_{1}) , say r_{1} , then d(c_{1},r_{1})\geq\left\lfloor\frac{|V(C)|}{2}\right\rfloor . Let c_{i} be the vertex occupied by the cop in his i^{\text{th}} move and let r_{i} be an antipodal vertex of a shadow of c_{i} that is occupied by the robber in his i^{\text{th}} move (note that such vertex exists by the induction hypothesis). Let c_{i+1} be the neighbor of c_{i} occupied by the cop in his next move. Since r_{i}\in A(\sigma(c_{i})) and c_{i}c_{i+1}\in E(G) , by Remark 17 there exists r_{i+1}\in A(\sigma(c_{i+1})) such that r_{i+1}\in N[r_{i}] . Hence, if the robber moves to r_{i+1} , he has a strategy to be at distance \left\lfloor\frac{|V(C)|}{2}\right\rfloor from the cop after each of his moves and thus to stay at distance \left\lfloor\frac{|V(C)|}{2}\right\rfloor-1 from the cop at each time of the game. Thus \rc(G)\geq\left\lfloor\frac{|V(C)|}{2}\right\rfloor-1 . For the converse, let G^{*} be the dual of G and let G^{\prime}=G^{*}-\{F\} , where F is a vertex of G^{*} that represents the outer face of G . Then G^{\prime} is a tree [ 22 ] . We will present a strategy for the cop which will ensure that cop wins the cop and robber game with radius of capture \left\lfloor\frac{|V(C)|}{2}\right\rfloor-1 . Let c_{1} and r_{1} be the vertices occupied by the cop and robber in their first moves, respectively. Let F_{1} be a face containing c_{1} and F_{1}^{\prime} a face containing r_{1} . Let R_{1}^{\prime} be the shortest F_{1},F_{1}^{\prime} -path in G^{\prime} and let R_{1} be a shortest c_{1},r_{1} -path in G . Then cop has the strategy to move from c_{1} to its neighbor on R_{1}. In a similar way, for any i>1 , let c_{i} and r_{i} be the vertices occupied by the cop and the robber in their i^{\text{th}} move, respectively. Let F_{i} be a face containing c_{i} and F_{i}^{\prime} a face containing r_{i} . Let R_{i}^{\prime} be the shortest F_{i},F_{i}^{\prime} -path in G^{\prime} and let R_{i} be a shortest c_{i},r_{i} -path in G . Then the cop’s strategy is to move from c_{i} to its neighbor on R_{i} . Note, this vertex is on the face F^{\prime} which lies on R_{i}^{\prime} . Since G is outerplanar there exists i such that c_{i} and r_{i} are on the same inner face of G . Thus d_{G}(c_{i},r_{i})\leq\left\lfloor\frac{|V(F^{\prime\prime})|}{2}\right\rfloor\leq\left\lfloor\frac{|V(C)|}{2}\right\rfloor . Hence, after the cop’s next move the distance between the cop and the robber is at most \left\lfloor\frac{|V(F^{\prime\prime})|}{2}\right\rfloor-1 , which implies that \rc(G)\leq\left\lfloor\frac{|V(C)|}{2}\right\rfloor-1 . ∎ 5.2 Sierpiński graphs For integers n\geq 0 and k\geq 1 , the Sierpiński graph S(n,k) is the graph with vertex set V(S(n,k))=[k]^{n} and edge set defined recursively as E(S(0,k))=\emptyset and E(S(n,k))=\{\{ix,iy\}\mid i\in[k],\{x,y\}\in E(S(n-1,k))\}\cup\{\{ij^{n-1},ji^{n-1}\}\mid i,j\in[k],i\neq j\}. For example, S(1,3)\cong K_{3} and S(3,3) is presented in Figure 2 . For more on Sierpiński graphs see for example [ 15 ] , and for results about the cop number of Sierpiński graphs, see [ 10 ] . 111 222 333 211 122 311 133 233 322 223 232 323 332 221 212 231 213 121 112 131 113 123 132 331 313 321 312 Figure 2: The Sierpiński graph S(3,3) . Theorem 18 . If n\geq 3 is an integer, then \rc(S(n,k))=3\cdot 2^{n-2}-1 . Proof. It is known [ 19 ] that \rad(S(n,k))=(2^{k-1}-1)2^{n-k+1} if n\geq k , thus \rad(S(n,3))=3\cdot 2^{n-2} . Thus by Theorem 3 we know that \rc(S(n,k))\leq 3\cdot 2^{n-2}-1 . To prove the equality we provide a strategy for the robber. Consider the following map \sigma^{1}_{n} from V(S(n,3)) to B=\{x\in V(S(n,3))\mid 1\notin x\} . Let \sigma^{1}_{n}(1^{n})=23^{n-1} . For 11x\in V(S(n,3)) , if 11x is closer to 12^{n-1} than to 13^{n-1} , then \sigma^{1}_{n}(11x)=23^{n-1} , and otherwise, \sigma^{1}_{n}(11x)=32^{n-1} . For 12x\in V(S(n,3)) , if 12x is at distance d from 12^{n-1} , then \sigma^{1}_{n}(12x) is the vertex in \{2y\in V(S(n,k))\mid 1\notin y\} that is at distance 2^{n-2}-1-d from 23^{n-1} (note that \max\{d(12x,12^{n-1})\mid x\in S(n-2,3)\}=2^{n-2}-1 ). For 13x\in V(S(n,3)) , if 13x is at distance d from 13^{n-1} , then \sigma^{1}_{n}(13x) is the vertex in \{3y\in V(S(n,k))\mid 1\notin y\} that is at distance 2^{n-2}-1-d from 32^{n-1} . For jx\in V(S(n,k)) , j\neq 1 , \sigma^{1}_{n}(jx)=j\sigma^{1}_{n-1}(x) . We also define \sigma^{1}_{1}(1)=\sigma^{1}_{1}(2)=2 and \sigma^{1}_{1}(3)=3 . Observe that if xy\in E(S(n,3)) , then \sigma^{1}_{n}(x)=\sigma^{1}_{n}(y) or \sigma^{1}_{n}(x)\sigma^{1}_{n}(y)\in E(S(n,3)[B]) . Notice also that analogously we can define \sigma^{2}_{n}\colon V(S(n,3))\to\{x\in V(S(n,3))\mid 2\notin x\} and \sigma^{3}_{n}\colon V(S(n,3))\to\{x\in V(S(n,3))\mid 3\notin x\} . The following vertices in S(n,3) induce a cycle C : \{1x\mid 1\notin x\}\cup\{2x\mid 2\notin x\}\cup\{3x\mid 3\notin x\} . Cycle C is of length 3\cdot 2^{n-1} . Recall that S(n,3) consists of three copies of S(n-1,3) together with edges \{12^{n-1},21^{n-1}\} , \{23^{n-1},32^{n-1}\} and \{31^{n-1},13^{n-1}\} connecting them, and that C contains all these three connecting edges and a path from each copy of S(n-1,3) . Define the map \sigma\colon V(S(n,3))\to C as \sigma(x_{1}\ldots x_{n})=x_{1}\sigma^{x_{1}}_{n-1}(x_{2}\ldots x_{n}). It follows from the properties of \sigma^{i}_{n} that if xy\in E(S(n,3)) , then \sigma(x)=\sigma(y) or \sigma(x)\sigma(y)\in E(S(n,3)[C]) . As C is a cycle of even length, every vertex on C has a well-defined antipodal vertex. Robber’s strategy when the game is played on S(n,3) is the following: if cop is on vertex c , robber moves to (or stays on) the antipodal vertex of \sigma(c) on C . The properties of \sigma imply that this strategy is well-defined and that d(c,r)\geq d(\sigma(c),\sigma(r)) for every position c of the cop and r of the robber. Thus robber is always at least \frac{|C|}{2}-1=3\cdot 2^{n-2}-1 away from the cop. ∎ Note that Theorem 18 essentially states that \rc(S(n,3))=\rad(S(n,3))-1 . It is not hard to see that this holds for n\in\{0,1,2\} as well using that \rad(S(n,k))=2^{n}-1 if nk for any i\in\{1,\ldots,\ell-1\} and d(c_{i+1},r_{i})>k for any i\in\{1,\ldots,\ell-2\} . We need to prove that they can continue moving and stay at distance at least k after each of the cop’s moves and at distance at least k+1 after each of the robber’s moves. Suppose that both players continue moving with accordance to the rules of the game. Clearly, if d(c_{i},r_{i})\geq k+1 , then d(c_{i+1},r_{i})\geq k , as c_{i+1}\in N[c_{i}] . Suppose that there exists integer j such that d(c_{j+1},r_{j})\geq k and r_{j} has no neighbor that is at distance at least k+1 from c_{j+1} . Hence, d(c_{j+1},r_{j+1})\leq k and thus cop can for his next move select a neighbor c_{j+2} of c_{j+1} from a shortest c_{j+1},r_{j+1} -path. Hence d(c_{j+2},r_{j+1})