Camino Balbuena, Florent Foucaud, Adriana Hansberg
Published 2014-07-27Version 1
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 meet these bounds.
Sufficient conditions for a digraph to admit a $(1,\leq\ell)$-identifying code
Embedding a Forest in a Graph
Identifying codes of the direct product of two cliques
![QR code for arXiv:1407.7263 [math.CO]](http://oss.arxitics.com/images/favicon.svg)