DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

C. Balbuena, C. Dalfó and B. Martínez-Barona

Title:

Sufficient conditions for a digraph to admit a $(1,\leq\ell)$-identifying code

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-11-09, Revised: 2019-03-05, Accepted: 2019-03-05, https://doi.org/10.7151/dmgt.2218

Abstract:

A $(1,\le \ell)$-identifying code in a digraph $D$ is a subset $C$ of vertices of $D$ such that all distinct subsets of vertices of cardinality at most $\ell$ have distinct closed in-neighbourhoods within $C$. In this paper, we give some sufficient conditions for a digraph of minimum in-degree $\delta^-\ge 1$ to admit a $(1,\le \ell)$-identifying code for $\ell\in\{\delta^-, \delta^-+1\}$. As a corollary, we obtain the result by Laihonen that states that a graph of minimum degree $\delta\ge 2$ and girth at least 7 admits a $(1,\le \delta)$-identifying code. Moreover, we prove that every $1$-in-regular digraph has a $(1,\le 2)$-identifying code if and only if the girth of the digraph is at least 5. We also characterize all the 2-in-regular digraphs admitting a $(1,\le \ell)$-identifying code for $\ell\in\{2,3\}$.

Keywords:

graph, digraph, identifying code

PDF
Close