Erschienen:
The Electronic Journal of Combinatorics, 2015
Erschienen in:The Electronic Journal of Combinatorics
Sprache:
Nicht zu entscheiden
DOI:
10.37236/4562
ISSN:
1077-8926
Entstehung:
Anmerkungen:
Beschreibung:
<jats:p>Locating-dominating sets and identifying codes are two closely related notions in the area of separating systems. Roughly speaking, they consist in a dominating set of a graph such that every vertex is uniquely identified by its neighbourhood within the dominating set. In this paper, we study the size of a smallest locating-dominating set or identifying code for graphs of girth at least 5 and of given minimum degree. We use the technique of vertex-disjoint paths to provide upper bounds on the minimum size of such sets, and construct graphs who come close to meeting these bounds.</jats:p>