Locating and identifying codes in circulant networks

A set S of vertices of a graph G is a dominating set of G if every vertex u of G is either in S or it has a neighbour in S. In other words, S is dominating if the sets S boolean AND N vertical bar u vertical bar where u is an element of V(G) and N vertical bar u vertical bar denotes the closed neighbourhood of u in G, are all nonempty. A set S subset of V(C) is called a locating code in G, if the sets S boolean AND N vertical bar u vertical bar where u is an element of V (G) \ S are all nonempty and distinct. A set S subset of V(C) is called an identifying code in G, if the sets S boolean AND N vertical bar u vertical bar where u is an element of V (G) are all nonempty and distinct. We study locating and identifying codes in the circulant networks C-n (1, 3). For an integer n >= 7, the graph C-n(1. 3) has vertex set Z(n), and edges xy where x, y is an element of Z(n) and vertical bar x - y vertical bar is an element of {1, 3}. We prove that a smallest locating code in C-n(1. 3) has size [n/3] + c, where c is an element of {0, 1}, and a smallest identifying code in C-n (1, 3) has size inverted right perpendicular4n/11inverted left perpendicular + c', where c' is an element of {0, 1}. (C) 2013 Elsevier B.V. All rights reserved.