Locating-dominating codes in cycles

Abstract

The smallest cardinality of an r-locating-dominating code in a cycle C_n of length n is denoted by M_r^{LD}(C_n). In this paper, we prove that for any r geq 5 and n geq n_r when n_r is large enough (n_r=mathcal{O}(r^3)) we have n/3 leq M_r^{LD}(C_n) leq n/3+1 if n equiv 3 pmod{6} and M_r^{LD}(C_n) = lceil n/3 ceil otherwise. Moreover, we determine the exact values of M_3^{LD}(C_n) and M_4^{LD}(C_n) for all n.