Sufficient Conditions for a Digraph to Admit A (1, ≤ ℓ)-Identifying Code
A (1, ≤ ℓ)-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 ℓ have distinct closed in-neighbourhoods within C. In this paper, we give some sufficient conditions for a digraph of minimum in-degree δ− ≥ 1 to admit a (1, ≤...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2021-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2218 |
| _version_ | 1797704384428113920 |
|---|---|
| author | Balbuena Camino Dalfó Cristina Martínez-Barona Berenice |
| author_facet | Balbuena Camino Dalfó Cristina Martínez-Barona Berenice |
| author_sort | Balbuena Camino |
| collection | DOAJ |
| description | A (1, ≤ ℓ)-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 ℓ have distinct closed in-neighbourhoods within C. In this paper, we give some sufficient conditions for a digraph of minimum in-degree δ− ≥ 1 to admit a (1, ≤ ℓ)-identifying code for ℓ ∈ {δ−, δ− + 1}. As a corollary, we obtain the result by Laihonen that states that a graph of minimum degree δ ≥ 2 and girth at least 7 admits a (1, ≤ δ)-identifying code. Moreover, we prove that every 1-in-regular digraph has a (1, ≤ 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, ≤ ℓ)-identifying code for ℓ ∈ {2, 3}. |
| first_indexed | 2024-03-12T05:19:35Z |
| format | Article |
| id | doaj.art-47d00de7bdc640f7a8ef6c07f6508836 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T05:19:35Z |
| publishDate | 2021-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-47d00de7bdc640f7a8ef6c07f65088362023-09-03T07:47:21ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922021-11-0141485387210.7151/dmgt.2218Sufficient Conditions for a Digraph to Admit A (1, ≤ ℓ)-Identifying CodeBalbuena Camino0Dalfó Cristina1Martínez-Barona Berenice2Departament d’Enginyeria Civili Ambiental Universitat Politècnica de Catalunya Barcelona, Catalonia, SpainDepartament de Matemàtica, Universitat de Lleida Igualada (Barcelona), Catalonia, SpainDepartament d’Enginyeria Civili Ambiental Universitat Politècnica de Catalunya Barcelona, Catalonia, SpainA (1, ≤ ℓ)-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 ℓ have distinct closed in-neighbourhoods within C. In this paper, we give some sufficient conditions for a digraph of minimum in-degree δ− ≥ 1 to admit a (1, ≤ ℓ)-identifying code for ℓ ∈ {δ−, δ− + 1}. As a corollary, we obtain the result by Laihonen that states that a graph of minimum degree δ ≥ 2 and girth at least 7 admits a (1, ≤ δ)-identifying code. Moreover, we prove that every 1-in-regular digraph has a (1, ≤ 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, ≤ ℓ)-identifying code for ℓ ∈ {2, 3}.https://doi.org/10.7151/dmgt.2218graphdigraphidentifying code05c6905c20 |
| spellingShingle | Balbuena Camino Dalfó Cristina Martínez-Barona Berenice Sufficient Conditions for a Digraph to Admit A (1, ≤ ℓ)-Identifying Code Discussiones Mathematicae Graph Theory graph digraph identifying code 05c69 05c20 |
| title | Sufficient Conditions for a Digraph to Admit A (1, ≤ ℓ)-Identifying Code |
| title_full | Sufficient Conditions for a Digraph to Admit A (1, ≤ ℓ)-Identifying Code |
| title_fullStr | Sufficient Conditions for a Digraph to Admit A (1, ≤ ℓ)-Identifying Code |
| title_full_unstemmed | Sufficient Conditions for a Digraph to Admit A (1, ≤ ℓ)-Identifying Code |
| title_short | Sufficient Conditions for a Digraph to Admit A (1, ≤ ℓ)-Identifying Code |
| title_sort | sufficient conditions for a digraph to admit a 1 ≤ l identifying code |
| topic | graph digraph identifying code 05c69 05c20 |
| url | https://doi.org/10.7151/dmgt.2218 |
| work_keys_str_mv | AT balbuenacamino sufficientconditionsforadigraphtoadmita1lidentifyingcode AT dalfocristina sufficientconditionsforadigraphtoadmita1lidentifyingcode AT martinezbaronaberenice sufficientconditionsforadigraphtoadmita1lidentifyingcode |