Olivier Delmas

Sylvain Gravier

Mickael Montassier

Aline Parreau

On two variations of identifying codes 6

Keywords: identifying codes, cycles, metric basis

Identifying codes have been introduced in 1998 to model fault-detection in multiprocessor systems. In this paper, we introduce two variations of identifying codes: weak codes and light codes. They correspond to fault-detection by successive rounds. We give exact bounds for those two definitions for the family of cycles.

Introduction

Identifying codes are dominating sets having the property that any two vertices of the graph have distinct neighborhoods within the identifying code. Also, they can be used to uniquely identify or locate the vertices of a graph. Identifying codes have been introduced in 1998 in [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF] to model fault-detection in multiprocessor systems. Numerous papers already deal with identifying codes (see e.g. [13] for an up-to-date bibliography). A multiprocessor system can be modeled as a graph where vertices are processors and edges are links between processors. Assume now that at most one of the processors is defective, we would like to locate it by testing the system. For this purpose, we select some processors (constituting the code) and have them test their r-neighborhoods (i.e. the processors at distance at most r). The processor sends an alarm if it detects a fault in its neighborhood. We require that we can, with these answers, tell if there is a faulty processor and, in this case, locate it uniquely. This corresponds exactly to finding an identifying r-code of the graph of the system.

Assume now that a processor can restrict its tests to its i-neighborhood for i ∈ 0, r . Then, we can have a detection process by rounds: at the first step, the selected processors test their 0-neighborhoods, then they test their 1-neighborhoods, . . . , until the r-neighborhoods. We stop the process when we can locate the faulty processor. We introduce in this paper weak r-codes (resp. light r-codes) that will model this process without memory, i.e. to identify a faulty processor at the round i, the supervisor does not need to remember the collected information of the rounds j < i (resp. with memory, i.e. to identify a faulty processor at the round i, the supervisor needs to remember the collected information of the rounds j < i) and study them for the family of cycles.

Let us give some notations and definitions. We denote by G = (V, E) a simple non oriented graph having vertex set V and edge set E. Let x and y be two vertices of G. The distance d(x, y) between x and y is the number of edges of a shortest path between x and y. Let r be an integer. The ball centered on x of radius r, denoted by B r (x) is defined by B r (x) = {y ∈ V | d(x, y) ≤ r}.

An r-dominating set of G is a subset C ⊆ V such that ∪ c∈C B r (c) = V . This means that each vertex of G is at distance at most r of a vertex of C. We say that a subset C ⊆ V r-separates x and y if and only if B r (x) ∩ C = B r (y) ∩ C (we will also say in this case that "x and y are separated by C for radius r" or that "x is separated from y by C for radius r"). A set C r-identifies x if and only if it r-separates x from all the other vertices.

(1) Identifying r-code. An identifying r-code of G is an r-dominating set C ⊆ V that r-identifies all the vertices:

∀x ∈ V, ∀y = x ∈ V, B r (x) ∩ C = B r (y) ∩ C (2) Weak r-code. A weak r-code of G is a r-dominating set C ⊆ V such that each vertex x is r x -identified by C for some radius r x ∈ 0, r : ∀x ∈ V, ∃r x ∈ 0, r , s.t. ∀y = x ∈ V, B rx (x) ∩ C = B rx (y) ∩ C (3) Light r-code. A light r-code of G is a r-dominating set C ⊆ V such that each pair (x, y) of vertices is r xy -separated by C for some radius r xy ∈ 0, r : ∀x ∈ V, ∀y = x ∈ V, ∃r xy ∈ 0, r , s.t. B rxy (x) ∩ C = B rxy (y) ∩ C Figure 1
gives an example of a weak 2-code of P 5 (elements of the code are in black, as in all the figures). Indeed, vertices v 3 and v 4 are identified for radius 0, vertices v 2 and v 5 are identified for radius 1 and vertex v 1 is identified for radius 2. But this code is not an identifying 2-code of P 5 : vertices v 2 , v 3 , v 4 and v 5 are not separated for radius 2. Figure 2 gives a light 2-code of P 5 which is not a weak 2-code: vertex v 2 is separated from vertex v 1 only for radius 0 and for this radius, vertex v 2 is not separated from v 3 .

v 1 v 2 v 3 v 4 v 5 Figure 1: A weak 2-code that is not an identifying 2-code v 1 v 2 v 3 v 4 v 5 Figure 2: A light 2-code that is not a weak 2-code
A code C is said to be optimum if its cardinality is minimum. We denote by IC r (G) (resp. WC r (G), LC r (G)) the cardinality of an optimum identifying (resp. weak, light) r-code. An identifying r-code is a weak r-code and a weak r-code is a light r-code. This implies the following inequality: IC r (G) ≥ WC r (G) ≥ LC r (G). For all graphs and for any r, there exits a weak r-code and a light r-code (using for instance all the vertices as the code), whereas this is not true for identifying codes.

Let us now give some bounds for weak codes. Theorem 1. Let r and k be two integers and w r (k) be the maximum order of a graph G such that G has a weak r-code of size k. We have:

w r (k) = k + r(2 k -2)

Proof

First, we construct a graph H k r in the following way (see Figure 3 for r = 4 and k = 3). The graph H k r has vertex set C ∪ I 1 ∪ ... ∪ I r where C = {1, ..., k} and I j has size 2 k -2 for 1 ≤ j ≤ r. Each vertex of I j corresponds to a non-empty strict subset of {1, ..., k}. Each vertex of I 1 is linked to the vertices of C that form its subset, and each vertex of I j for j > 1 is linked to the vertex of I j-1 that corresponds to the same subset. Furthermore, C induce a clique in H k r . The graph H k r has order k + r(2 k -2) and one can check that C is a weak r-code of H k r (a vertex of I j is identified for radius j). So w r (k

) ≥ k + r(2 k -2).
Now let G be a graph and C be a weak r-code size k of G. Let us try to maximize the number of identified vertices for each radius i ≤ r.

• For radius 0, only the k vertices of C can be identified.

• For radius 1, at most 2 k additionnal vertices can be identified (one for each subset of C). However, it is not possible to have all the subsets. Indeed, all the elements of {B 1 (c) ∩ C | c ∈ C} cannot be used to identify a vertex not in C for radius 1.

If 2 k -1 additional vertices are identified at radius 1, that means that {B 1 (c)∩C |c ∈ C} contains only one element, which is necessarily the whole set C. Then all the strict subsets of {1, ..., k} are used to identify a vertex for radius 1, in particular, one vertex is identified by the emptyset and so is not 1-dominated by C. As the set C must be an r-dominating set, then r ≥ 2. Furthermore, if we try to add a new vertex x in G, then necessarily, B 1 (x) ∩ C = C and x will not be identified for any radius. So, G has order k + (2 k -1) and r ≥ 2. A contradiction with the bound w r (k) ≥ k + 2(2 k -2) for r ≥ 2, given by the construction of the graph H k 2 . It follows that at most 2 k -2 additionnal vertices are identified for radius 1 in G. • For radius 2 ≤ i ≤ r, using a similar process, we can show that at most 2 k -2 vertices are identified at round i.

Summing the number of identified vertices at each round, we obtain that G has order at most

k + r(2 k - 2). It follows that w r (k) = k + r(2 k -2). 2 C I 1 I 2 I 3 I 4 1 2 3 Figure 3:
The graph H 3 4 -Extremal case for a graph with a weak 4-code of size 3

Light r-codes are related to other locating notions: a light 1-code is a 1-locating dominating code [START_REF] Colbourn | Locating dominating sets in series parallel networks[END_REF] for which we require that only pairs of vertices not in the code are 1-separated by C. The notion of light r-codes is a generalization of the notion of metric basis. A subset C of vertices is a metric basis if every pair of vertices of the graph is separated by a vertex of C for some radius (there is no bound on the radius). The metric dimension of a graph G, denoted by dim(G), is the cardinal of a minimum metric basis. A light r-code is a metric basis, so LC r (G) ≥ dim(G). If r is greater than the diameter of G, i.e. the largest distance between two vertices of G, then a light r-code is exactly a metric basis. For a detailed review about metric basis, see [START_REF] Chartrand | Resolvability in graphs and the metric dimension of a graph[END_REF]. As for metric basis, we do not have good bounds of the extremal size of a graph that has light r-codes of size k.

The optimization problems of finding optimum identifying codes [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is np-hard[END_REF] and optimum metric bases [START_REF] Khuller | Landmarks in graphs[END_REF] are NP-complete. Finding optimum light codes is also NP-complete because if r is larger than the diameter of the graph, then it is equivalent to metric bases. Therefore, identifying codes and metric bases have been studied in particular classes of graphs (see e.g. [START_REF] Bertrand | 1-identifying codes on trees[END_REF][START_REF] Charon | A linear algorithm for minimum 1-identifying codes in oriented trees[END_REF][START_REF] Charon | The minimum density of an identifying code in the king lattice[END_REF][START_REF] Honkala | On identifying codes in binary hamming spaces[END_REF]).

For cycles, although metric bases problem in cycles is not difficult (the dimension of a cycle is 2), the case of identifying codes is not as easy: the complete study of cycles has just been finished in [START_REF] Junnila | Optimal identifying codes in cycles and paths[END_REF] after numerous contributions (see e.g. [START_REF] Bertrand | Identifying and locating-dominating codes on chains and cycles[END_REF][START_REF] Gravier | Identifying codes of cycles[END_REF][START_REF] Xu | Identifying codes of cycles with odd orders[END_REF]). We focus on the case of weak and light r-codes.

In this paper, we give exact value for WC r (Section 2) and LC r (Section 3) for the class of cycles. In weak codes, we assign a radius to each vertex to separate it from other vertices whereas we can assign up to r + 1 radii to a vertex with light r-codes. We show that 3 radii per vertex is actually sufficient to separate it from all the other vertices. We adress in Section 4 the question of the optimum size of a code requiring only 2 stored radii per vertex.

Weak r-codes of cycles

In the following, we will denote by C n the cycle of size n and by {v 0 , v 1 , . . . , v n-1 } the set of its vertices. We first assume that n ≥ 2r + 2. Lemma 1. Let S be a set of 2r + 2 consecutive vertices on C n . If C is a weak r-code of C n , then S contains at least two elements of C.

Proof

Without loss of generality, S = {v 0 , v 1 , . . . , v 2r+1 }. Assume S contains a single element of the code, say a = v i , w.l.o.g. i ≤ r (see Figure 4).

S

x y z a We focus on the vertices In the following, we set n = (2r + 2)p + R, with 0 ≤ R ≤ 2r + 1 and p ≥ 1 (by assumption, n ≥ 2r + 2).

x = v r-1 , y = v r and z = v r+1 . Then, B r (y) ⊆ S and B r (z) ⊆ S. Let t = d(a, y) = r -i. For all r ′ ∈ 0, t-1 , B r ′ (y)∩C = B r ′ (z)∩C = ∅. For all r ′ ∈ t+1, r , B r ′ (y)∩C = B r ′ (z)∩C = {a}. Hence r y = r z = t. It follows that B t (y) ∩ C = {a} must be different from B t (x) ∩ C.
Then Corollary 1 can be reformulated as: if C is a weak r-code of C n , then we have

• if R = 0, then |C| ≥ 2p; • if 1 ≤ R ≤ r + 1, then |C| ≥ 2p + 1; • if r + 2 ≤ R ≤ 2r + 1, then |C| ≥ 2p + 2.
Lemmas 2 to 4 give some constructive upper bounds. Moreover, Lemmas 2 to 5 provides exact values of WC r (C n ). Lemma 2. If n = (2r + 2)p, then C n has a weak r-code with cardinality 2p = n/(r + 1); moreover, this code is optimum.

Proof

We construct the code by repeating the pattern depicted by Figure 5. More precisely, let

C = {v i | i ≡ r [2r + 2] or i ≡ r + 1 [2r + 2]}. The set C has cardinality 2p. The set C r-dominates all the vertices of C n . Let r v k = r -k if k ∈ 0, r and r v k = k -(r + 1) if k ∈ r + 1, 2r + 1 (the indices of the vertices of C n are taken modulo 2r + 2). Then for all pair of vertices v k , v l , k = l, we have B rv k (v k ) ∩ C = B rv k (v l ) ∩ C.
Hence C is an r-dominating set that r v k -identifies the vertex v k . It follows that C is a weak r-code. This code is optimum by Corollary 1. Figure 6 gives an example of such a code in C 12 .

2

We can easily extend this construction to the general case:

v 4 v 3 v 2 v 1 v 0 v 11 v 10 v 9 v 8 v 7 v 6 v 5 Figure 6: An optimum weak 2-code of C 12 v 4 v 3 v 2 v 1 v 0 v 12 v 11 v 10 v 9 v 8 v 7 v 6 v 5 Figure 7: An optimum weak 2-code of C 13 Proof Let R = 1 and C = {v i | i ≡ r [2r + 2] or i ≡ r + 1 [2r + 2]} ∪ {v n-1 }.
Then C is a weak r-code of C n and |C| = 2p + 1. (See Figure 7.) Assume now that R ≥ 1 and take for code

C = {v i | i ≡ r[2r + 2] or i ≡ r + 1[2r + 2]} if R ≥ r + 2 and C = {v i | i ≡ r[2r + 2] or i ≡ r + 1[2r + 2]} ∪ {v n-2 , v n-1 } otherwise. Then C is a weak r-code of C n . 2
In some cases, the aforementioned codes are not optimum: Figure 8 (resp. Figure 9) shows an example of an optimum weak r-code for (r, R) The next lemma shows that the lower bound of Corollary 1 is not sharp for 2 ≤ R ≤ r + 1 and (r, R) = (1, 2) or (2, 2), this implies that in these cases, codes of Lemma 3 are optimum.

= (1, 2) (resp. (r, R) = (2, 2)). v 4 v 3 v 2 v 1 v 0 v 9 v 8 v 7 v 6 v 5 Figure 8: An optimum weak 1-code of C 10 v 4 v 3 v 2 v 1 v 0 v 7 v 6 v 5

Proof

Assume that there is a weak r-code C of C n of cardinality 2p + 1. First, observe:

(O.1) In a set of R consecutive vertices of C n , there must be at most one vertex of C. Otherwise, in the rest of C n , there are at most 2p -1 vertices of the code in a set of (2r + 2)p consecutive vertices which contradicts Lemma 1. In particular there is no pair of consecutive vertices of C.

(O.2) For similar reasons, in a set of 2r + 2 + R consecutive vertices of C n , there must be at most 3 vertices of C.

Let M be the maximum size of a set of consecutive vertices not in C and let S M be a set of M consecutive vertices not in C. We know by (O.1) that M ≥ R -1. Moreover M > 1; indeed, if M = 1, then R = 2 and the code is exactly one vertex over 2, so |C| = n 2 = 2p + 1, n = 4p + 2 and (r, R) = (1, 2). Let us denote c 1 and c 2 the two elements of the code bounding S M , let S 1 and S 2 be the two maximal sets of consecutive vertices not in C who are before c 1 and after c 2 , and finally c 0 and c 3 the two vertices of the code who are before S 1 and after S 2 (see Figure 10). • Observe that p ≥ 1, so C has cardinality at least 3 and observe by (O.1) that S 1 and S 2 are not empty.

S 1 S M S 2 c 0 c 1 c 2 c 3 x y z
Hence, the elements c 1 , c 2 , c 3 may be supposed distincts and so on for elements c 0 , c 1 and c 2 , but note that c 0 and c 3 may denote the same vertex. Consider (r, R) = (1, 2) or (2, 2) and R = 2, then r ≥ 3 and so M ≥ 5. Let v 1 and v 2 be the two consecutive vertices in S M following c 1 (see Figure 11). We have d(v 2 , c 2 ) = M -1 > r and d(v 1 , c 2 ) > r so v 1 and v 2 can only be separated by elements of the code on the left of v 1 and v 2 . Let r v1 be the radius that identifies v 1 . There must be an element of the code at distance exactly r v1 of v 1 to separate v 1 and v 2 , and for similar reasons, there must be an element of the code at distance r v1 + 1 of v 1 to separate v 1 from c 1 . This implies that two elements of the code are consecutives vertices in C n , which contradicts (O.1). 2

• Observe by (O.1) that |S 1 | ≥ R -1, |S 2 | ≥ R -1, M ≥ R -1. Let us denote S the set S 1 ∪ {c 1 } ∪ S M ∪ {c 2 } ∪ S 2 . • Observe that |S| ≥ 2r + 3.
M c 0 c 1 c 2 c 3 v 1 v 2 w x y z
We are now able to compute WC r (C n ) for all n ≥ 2r + 2. Our results are summarized in the following theorem: Theorem 2. Let r be an integer and n = (2r + 2)p + R, with 0 ≤ R ≤ 2r + 1 and p ≥ 1, we have:

i) if R = 0, then WC r (C n ) = 2p, ii) if R = 1 or if r ≤ 2 and R = 2, then WC r (C n ) = 2p + 1, iii) otherwise, R ≥ 2 and (r, R) = (1, 2) or (2, 2), then WC r (C n ) = 2p + 2.
The following lemma completes the study for the small cases: Lemma 6. Let r and n be integers with 3

≤ n ≤ 2r + 1, then WC r (C n ) = 2.

Proof

The code cannot be a single vertex, otherwise its two neighbors are not i-separated for any i, so WC r (C n ) ≥ 2. Two adjacent vertices form a weak r-code for any r, so WC r (C n ) = 2. Note that if n is odd, the antipodal vertex to the code in the cycle is identified by the empty set. 2

Light r-codes of cycles

We now study light r-codes of the cycle C n . In this section, we will first assume that n ≥ 3r + 2 and we will study the small values of n at the end of the section.

Proof

Let C be a light r-code of C n . Let us assume there is a set S of 3r + 2 consecutive vertices of C n containing only one element c of C. w.l.o.g., we denote S = {v 0 , v 1 , . . . , v 3r+1 } and c = v i with i < 2r. By Lemma 7, there is an element

c ′ at distance at most r + 1 of c. But c ′ / ∈ S so necessarily, c ′ ∈ {v -1 , v -2 , . . . , v -(r+1) } and i ≤ r. Then v 2r+1 is not r-dominated by any element of C, a contradiction. 2
It follows from Lemma 8:

Corollary 2. Let C be a light r-code of C n . Then |C| ≥ ⌈2n/(3r + 2)⌉.

In the following, let n = (3r + 2)p + R with 0 ≤ R ≤ 3r + 1 and p ≥ 1 (by assumption, n ≥ 3r + 2).

Then Corollary 2 can be reformulated as: if C is a light r-code of C n , then we have

• if R = 0, then |C| ≥ 2p, • if 0 < 2R ≤ 3r + 2, then |C| ≥ 2p + 1,
• otherwise, 2R > 3r + 2, and |C| ≥ 2p + 2.

We want to exhibit some optimum codes.

Theorem 3-i (resp. 3-ii, 3-iii) follows from Lemma 9 (resp. Corollary 2 and Lemma 10, and from Lemmas 10 and 11).

The next lemma completes the study for the small values of n:

Lemma 12. Let r and n be integers with 3

≤ n ≤ 3r + 1, then LC r (C n ) = 2.

Proof

A light r-code cannot be a single vertex otherwise the neighbors of the element of the code are not iseparated for any i. Two adjacent vertices form a light r-code for any n ≤ 2r + 2. For n > 2r + 2, take two vertices at distance r + 1. 2

With light r-codes, we can assign up to r + 1 radii to a vertex to separate it from all the other vertices. Actually, for cycles, we just need three radii: Proposition 1. Let C be a light r-code of C n and x be a vertex of C n . Assume that n > 2r + 1. There is a subset R x of 0, r of size at most 3 such that for all other vertices y of C n , there is r xy ∈ R x such that B rxy (x) ∩ C = B rxy (y) ∩ C.

Proof

Without loss of generality, we can assume that x = v 0 .

Assume first that there exist two vertices of the code, say a = v i and b = v j , such that -r ≤ i ≤ 0 ≤ j ≤ r (if x ∈ C, then we have a = b = x). Thus R x = {d(x, a), d(x, b)} separates x from all the other vertices: vertices x and v k are separated for radius d(x, a) if 0 < k < n/2 and for radius

d(x, b) if -n/2 < k < 0.
Otherwise, let a = v i be the element of the code closest to x. We can assume that 0 < i ≤ r. By Lemma 7 we know that there exists another element of the code b = v j such that i < j and ji ≤ r + 1. Then x is separated from all vertices not in B i (a) by radius i, and from all vertices in B i-1 (a) by radius i -1. It remains one vertex, v 2i , that is separated from x for radius d(v 2i , b) ≤ r. Finally the three radii i, i -1, d(v 2i , b) are enough to separate x from all vertices.

2

This proposition leads to the following question: what is the size of an optimum light r-code on C n that need to assign only 2 radii to each vertex? We solve this question in the next section.

Codes with 2 radii

A (2, 0, r )-code C of a graph G is a subset of vertices of G that r-dominates every vertex and such that for each vertex x, we can assign a set R x = {r x , r ′

x } of integers in 0, r such that every pair of distinct vertices (x, y) is r x or r ′

x -separated by C.

Proof

We focalize on a pattern S. Denote by c 1 and c 2 the two vertices of the code of S and assume that c 1 = v 0 . Then c 2 = v r-k+1 and the vertices of S are the vertices between v -r and v 2r-k+1 . Partition the vertices of S in five subsets: A 1 = {v -r , . . . , v -k-1 }, A 2 = {v -k , . . . , v -1 }, A 3 = {v 0 , . . . , v r-k+1 }, A 4 = {v r-k+2 , . . . , v r+1 } and A 5 = {v r+2 , . . . , v 2r-k+1 }. If r = 1, then A 2 and A 4 are empty; if r = 0, then A 3 is non empty and the other sets are empty. Let x be a vertex of S. Let R x the set of radii associated to x:

• if x ∈ A 1 , then set R x = {d(x, c 1 ), d(x, c 1 ) -1}; • if x ∈ A 2 , then set R x = {d(x, c 1 ), d(x, c 2 ) -1}; • if x ∈ A 3 , then set R x = {d(x, c 1 ), d(x, c 2 )}; • if x ∈ A 4 , then set R x = {d(x, c 1 ) -1, d(x, c 2 )}; • if x ∈ A 5 , then set R x = {d(x, c 2 ), d(x, c 2 ) -1}.
One can check that R x ⊂ 0, r in all cases. By symmetry, we just need to check that every vertex x of A 1 ∪ A 2 ∪ A 3 is separated from all the other vertices for a radius in R x .

If x ∈ A 1 , then x is separated from the vertices not in B d(x,c1) (c 1 ) for radius d(x, c 1 ) and from the vertices in B d(x,c1)-1 (c 1 ) for radius d(x, c 1 ) -1. Remains the vertex y at distance d(x, c 1 ) of c

1 . If x = v -i , with k + 1 ≤ i ≤ r, then y = v i and d(y, c 2 ) = r -k + 1 -i ≤ r -2k ≤ k + 1 ≤ d(x,

Proof

For r = 0, the lemma is true as all the vertices must be 0-dominated. The lemma is also true for r = 1, as a (2, 0, 1 )-code is a light 1-code. Now, let r ≥ 2. Notice that 3rk + 2 > 2r, thus S contains at least one vertex of C. By contradiction, assume that S contains only one vertex c of C, and w.l.o.g. assume c = v 0 . Let v -a be the first vertex of S and v b be the last vertex of S, a + b = 3rk + 1. We can assume that a ≤ b. C is also a light r-code so by Lemma 7 a ≤ r, then b ≥ 2rk + 1. C is r-dominating so b ≤ 2r, and then a As corollary, the code of Lemma 13 is optimum and we have the following lower bound, as for light and weak codes: Corollary 3. Let C be a (2, 0, r )-code of C n . Then |C| ≥ ⌈2n/s⌉ with s = 3r -⌊(r + 1)/3⌋ + 2 .

≥ r -k + 1. We have B r (v k ) ∩ C = B r (v k-1 ) ∩ C = B r (v k+1 ) ∩ C = {c} because d(v k , v -
It remains the case where s does not divide n, with similar arguments used for light codes, one can show that: Theorem 4. Let n, r, s, p, R be integers, set k = ⌊(r + 1)/3⌋, s = 3rk + 2 and n = sp + R, with 0 ≤ R < s. Then the size of an optimum (2, 0, r )-code of C n is:

i) 2p if R = 0; ii) 2p + 1 if R ≤ r + 1; iii) 2p + 2 otherwise.

Perspectives

Section 4 suggests the following definition that will generalize all the previous ones: Integer p corresponds to the number of radii we can assign to a vertex to separate it from all the others whereas the set R denotes the set of radii we can use. This definition unifies all the previous ones: a ridentifying code is a (1, {r})-identifying code, a weak r-code is a (1, 0, r )-identifying code, a light r-code is a (r + 1, 0, r )-identifying code, a r-locating dominating code is a (2, {0, r})-identifying code. Proposition 1 is equivalent to say that every (p, 0, r )-code in a cycle, with p ≥ 3 is a (3, 0, r )identifying code. Section 4 and Section 2 consider (2, 0, r )-identifying codes and (1, 0, r )-identifying codes of the cycle, respectively. Hence we solved the problem of finding an optimum (p, 0, r )-identifying code (for any p) in a cycle. However, the general problem of finding an optimum (p, R)-identifying codes in the cycle is still unknown.

Figure 4 :

 4 Figure 4: Notation of the proof (Lemma 1)

2 ACorollary 1 .

 21 Hence, B t (x) ∩ C must contain an element different from a, say b. Necessarily, b / ∈ S, this implies t = r and z is not r-dominated, a contradiction. first bound of WC r (C n ) directly follows from Lemma 1: Let C be a weak r-code of C n . Then |C| ≥ ⌈n/(r + 1)⌉.ProofIn C n there are n different sets S of 2r + 2 consecutives vertices. If C is a weak r-code, by Lemma 1, there are at least 2 vertices of the code in each set S. Each vertex of the code is counted exactly 2r + 2 times, so |C| ≥ ⌈2n/(2r + 2)⌉ = ⌈n/(r + 1)⌉.2

Lemma 3 .Figure 5 :

 35 Figure 5: The pattern for a weak r-code in the cycles C (2r+2)p with p ≥ 1

Lemma 4 .

 4 If (r, R) = (1, 2), then C n has an optimum weak 1-code of cardinality 2p + 1. If (r, R) = (2, 2), then C n has an optimum weak 2-code of cardinality 2p + 1.

Figure 9 : 8 Proof

 98 Figure 9: An optimum weak 2-code of C 8

Lemma 5 .

 5 If 2 ≤ R ≤ r + 1 and (r, R) = (1, 2) or[START_REF] Bertrand | 1-identifying codes on trees[END_REF][START_REF] Bertrand | 1-identifying codes on trees[END_REF], then C n does not have a weak r-code of cardinality 2p + 1.

Figure 10 :

 10 Figure 10: Notation of the proof (Lemma 5)

  Indeed, if c 0 and c 3 are different vertices, then {c 0 } ∪ S ∪ {c 3 } is a set with 4 vertices of the code, so, by (O.2) |S| + 2 > 2r + 2 + R ≥ 2r + 4. If c 0 and c 3 denote the same vertex, then S ∪ {c 3 } = V (C n ), p = 1 and |S| = n -1 = 2r + 1 + R ≥ 2r + 3. So there are three consecutive vertices x, y, z in S such that {B r (x) ∪ B r (y) ∪ B r (z)} ∩ C ⊆ {c 1 , c 2 } and y ∈ S M . To separate y and x, r y must be d(x, c 1 ) or d(y, c 2 ). To separate y and z, r y must be d(y, c 1 ) or d(z, c 2 ). Therefore, either r y = d(x, c 1 ) = d(z, c 2 ), or r y = d(y, c 2 ) = d(y, c 1 ). In all cases, M is odd and y is the middle element of S M , so d(y, c 1 ) = d(y, c 2 ). As M = 1 then M ≥ 3 and (x, z) ∈ S M × S M . Let d y denote d(y, c 1 ) in the following. Let w be the vertex just before x. Then B r (w) ∩ C ⊆ {c 0 , c 1 , c 2 }. To separate x from y, r x must be d(y, c 2 ) = d y or d(x, c 1 ) = d y -1. To separate x from w, r x must be d(w, c 1 ) = d y -2 or d(x, c 2 ) = d y + 1 or d(w, c 0 ). Necessarily, we have r x = d(w, c 0 ). This implies d(w, c 0 ) = r because d(w, c 0 ) = d(x, c 0 ) -1 ≥ r and r x ≤ r. Since d y ≤ r and r x = d y or r x = d y -1. It follows r x = d y = r. Therefore M = 2r -1, |S 1 | = 1, and finally R = 2. With similar arguments for z, we obtain the situation depicted by Figure 11.

S

Figure 11 :

 11 Figure 11: The sets S 1 , S 2 and S M after some deductions

Lemma 7 . 2 Lemma 8 .

 728 Let C be a light r-code of C n and c an element of C. There is another element of the code C at distance at most r + 1 of c. Proof Let x and y be the neighbors of c. As C is a light r-code, there is an integer r xy such that 0 ≤ r xy ≤ r and B rxy (x) ∩ C = B rxy (y) ∩ C. There consequently exists a vertex c ′ ∈ C such that, w.l.o.g., c ′ ∈ B rxy (x) and c ′ / ∈ B rxy (y). Moreover, c = c ′ because d(x, c) = d(c, y) = 1. It follows that d(c ′ , c) ≤ d(c ′ , x) + d(x, c) ≤ r xy + 1 ≤ r + 1. Let S be a set of 3r + 2 consecutive vertices on C n . If C is a light r-code of C n , then S contains at least two elements of C.

Lemma 13 .

 13 Let k = ⌊(r + 1)/3⌋ and s = 3rk + 2. If s divides n, then the code defined by repeating the pattern S depicted by Figure 13 is a (2, 0, r )-code of C n . r rk r

Figure 13 :

 13 Figure 13: The pattern S for a (2, 0, r )-code of the cycle Cn with n multiple of s (cf. Lemma 13)

2 Lemma 14 .

 214 c 1 ) by definition of k. Notice that d(x, c 2 ) > d(x, c 1 ), so x and y are separated for radius d(x, c 1 ). If x ∈ A 2 , then x is separated from the vertices not in B d(x,c1) (c 1 ) for radius d(x, c 1 ) and from the vertices in B d(x,c2)-1 (c 1 ) for radius d(x, c 2 ) -1. That covers all the vertices of the cycle.One can check by the same kind of arguments that x ∈ A 3 is also separated from all the other vertices for d(x, c 1 ) or d(x, c 2 ). Let C be a (2, 0, r )-code of C n . Let S be a set of s = 3r-k+2 vertices with k = ⌊(r+1)/3⌋. Then S contains at least two vertices of C.

  a ) = a + k ≥ r + 1 and d(v k , v b ) = bk ≥ 2r -2k + 1 ≥ r + 1. Then, v k and v k-1 are only separated for radius k -1, v k and v k+1 are only separated for radius k. So necessarily v k and v -k must be separated for radius k or k -1. That means there is a vertex of the code c ′ ∈ S different of c at distance at mostk of v -k . But d(c ′ , v -k ) = d(c ′ , v -a ) + d(v -a , v -k ) ≥ 1 + ak ≥ r -2k + 2 ≥ k + 1 (by definition of k), a contradiction.2

Definition 1 .

 1 Let p be an integer and R be a set of non-negative integers.A (p, R)-identifying code of a graph G = (V, E) is a subset C of V such that: (domination) ∀x ∈ V, ∃r ∈ R, B r (x) ∩ C = ∅ (identification) ∀x ∈ V, ∃R x ⊂ R, |R x | ≤ p, ∀y ∈ V, y = x, ∃r xy ∈ R x s.t.:B rxy (x) ∩ C = B rxy (y) ∩ C

This research is supported by the ANR Project IDEA • Identifying coDes in Evolving grAphs • ANR-08-EMER-007, 2009-2011. Email address: aline.parreau@ujf-grenoble.fr (Aline Parreau)

Proof

We construct the code by repeating the pattern S depicted by Figure 12. More precisely, let

Set C is a r-dominating set of size 2p and we just need to check that every pair of vertices is separated by C for some radius in 0, r . It is sufficient to prove it for all pairs (v i , v j ) in the pattern S, i.e. with (i, j) ∈ 0, 3r + 1 × 0, 3r + 1 . W.l.o.g. we study the case i < j, and we define r ij as follows:

We generalize this construction:

Proof

Consider the three following cases: (1) R ∈ 1, r + 1 , (2) R ∈ r + 2, 2r + 2 , and (3) R ∈ 2r + 3, 3r + 1 .

For each case, we define the code C as:

(1)

Proof

Assume that there is a code C of cardinality 2p + 1. First observe that in a set S of R consecutive vertices, there is at most one element of the code C. Otherwise, there will be only 2p -1 elements of the code in the rest of the cycle which can be divided in p disjoint sets of size 3r + 2. One of this set will have only one element of the code, a contradiction by Lemma 8. Now, take an element c of the code C, by Lemma 7 there is a vertex c ′ of the code at distance d ≤ r + 1 of c. Take the set S of all vertices between c and c ′ , c and c ′ included. S has cardinality at most r + 2 ≤ R and has two vertices of C, a contradiction. 2 Our results are summarized in the following theorem: Theorem 3. Let r be an integer and n = (3r + 2)p + R, with 0 ≤ R < 3r + 2, and p ≥ 1, we have:

iii) otherwise, R > r + 1 and then LC r (C n ) = 2p + 2.