A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On r-locating-dominating sets in paths
Tekijät: Honkala I
Kustantaja: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
Julkaisuvuosi: 2009
Journal: European Journal of Combinatorics
Tietokannassa oleva lehden nimi: EUROPEAN JOURNAL OF COMBINATORICS
Lehden akronyymi: EUR J COMBIN
Vuosikerta: 30
Numero: 4
Aloitussivu: 1022
Lopetussivu: 1025
Sivujen määrä: 4
ISSN: 0195-6698
DOI: https://doi.org/10.1016/j.ejc.2008.04.011
Tiivistelmä
Assume that G = (V, E) is a simple undirected graph, and C is a nonempty subset of V. For every v is an element of V, we define I(r)(v) = {u is an element of C | d(G)(u, v) <= r}, where d(G)(u, v) denotes the number of edges on any shortest path between u and v. If the sets I(r)(v) for v is not an element of C are pairwise different, and none of them is the empty set, we say that C is an r-locating-dominating set in G. It is shown that the smallest 2-locating-dominating set in a path with n vertices has cardinality inverted right perpendicular (n + 1)/3 inverted left perpendicular, which coincides with the lower bound proved earlier by Bertrand, Charon, Hudry and Lobstein. Moreover, we give a general upper bound which improves a result of Bertrand, Charon, Hudry and Lobstein. (C) 2008 Elsevier Ltd. All rights reserved.
Assume that G = (V, E) is a simple undirected graph, and C is a nonempty subset of V. For every v is an element of V, we define I(r)(v) = {u is an element of C | d(G)(u, v) <= r}, where d(G)(u, v) denotes the number of edges on any shortest path between u and v. If the sets I(r)(v) for v is not an element of C are pairwise different, and none of them is the empty set, we say that C is an r-locating-dominating set in G. It is shown that the smallest 2-locating-dominating set in a path with n vertices has cardinality inverted right perpendicular (n + 1)/3 inverted left perpendicular, which coincides with the lower bound proved earlier by Bertrand, Charon, Hudry and Lobstein. Moreover, we give a general upper bound which improves a result of Bertrand, Charon, Hudry and Lobstein. (C) 2008 Elsevier Ltd. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali