Locating-dominating codes in paths

Abstract

Bertrand, Charon, Hudry and Lobstein studied, in their paper in 2004 [1] r-locating-dominating codes in paths P(n). They conjectured that if r >= 2 is a fixed integer, then the smallest cardinality of an r-locating-dominating code in P(n), denoted by M(r)(LD) (P(n)), satisfies M(r)(LD)(P(n)) = [(n + 1)/3] for infinitely many values of n. We prove that this conjecture holds. In fact, we show a stronger result saying that for any r >= 3 we have M(r)(LD) (P(n)) = [(n + 1)/3] for all n >= n(r), when n(r) is large enough. In addition, we solve a conjecture on location-domination with segments of even length in the infinite path. (C) 2011 Elsevier B.V. All rights reserved.