Independent Locating-Dominating Sets in Pseudotrees
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911685358387200 |
|---|---|
| author | Cáceres, José Pelayo, Ignacio M. |
| author_facet | Cáceres, José Pelayo, Ignacio M. |
| contents | An ILD-set in a connected graph is a subset $S$ of vertices such that it is both independent and locating-dominating. The independent locating-dominating number of a graph G is the minimum cardinality of an ILD-set set of $G$.
A well-known fact is that any graph with girth at least 5 has an ILD-set, but that is not clear for graphs with girth 3 and 4. In this work, we prove that there are graphs with no ILD-sets for any order $n\geq 9$ and girth 4, also showing some sufficient conditions for a bipartite graph to contain an ILD-set.
Moreover, we focus our attention on trees and on unicyclic graphs, showing that every tree and every unicyclic graph contains ILD-sets, whenever in the latter case, it is twin-free. Finally, a number of bounds, realization theorems and algorithms to find an ILD-set in those families of graphs are provided. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_07361 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Independent Locating-Dominating Sets in Pseudotrees Cáceres, José Pelayo, Ignacio M. Combinatorics 05C12, 05C69, 05C85 G.2.2 An ILD-set in a connected graph is a subset $S$ of vertices such that it is both independent and locating-dominating. The independent locating-dominating number of a graph G is the minimum cardinality of an ILD-set set of $G$. A well-known fact is that any graph with girth at least 5 has an ILD-set, but that is not clear for graphs with girth 3 and 4. In this work, we prove that there are graphs with no ILD-sets for any order $n\geq 9$ and girth 4, also showing some sufficient conditions for a bipartite graph to contain an ILD-set. Moreover, we focus our attention on trees and on unicyclic graphs, showing that every tree and every unicyclic graph contains ILD-sets, whenever in the latter case, it is twin-free. Finally, a number of bounds, realization theorems and algorithms to find an ILD-set in those families of graphs are provided. |
| title | Independent Locating-Dominating Sets in Pseudotrees |
| topic | Combinatorics 05C12, 05C69, 05C85 G.2.2 |
| url | https://arxiv.org/abs/2605.07361 |