Locating-dominating codes in paths

: Exoo G, Junnila V, Laihonen T

Publisher: ELSEVIER SCIENCE BV

: 2011

: Discrete Mathematics

: DISCRETE MATHEMATICS

: DISCRETE MATH

: 17

: 311

: 17

: 1863

: 1873

: 11

: 0012-365X

DOI: https://doi.org/10.1016/j.disc.2011.05.004

: https://research.utu.fi/converis/portal/Publication/1348692

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.

LDonPathsDMRevision0511.pdf