Metraipolis › archive › dc_e81094fbeb14

A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set — arXiv:2610.03131

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.03131
License (as archived)
CC0-1.0
Archived
2026-10-06T08:25:02.836Z
SHA-256 of the archived text
303c5ca07384cc0e0506716d06f4c4f0c771338dca0ef6a8d0e11d64e313636c
Stable URL of this page
https://metraipolis.com/documento/dc_e81094fbeb14

How to cite

A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set — arXiv:2610.03131 — arXiv (en), https://arxiv.org/abs/2610.03131 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e81094fbeb14 (Metraipolis archive dc_e81094fbeb14, sha256 303c5ca07384cc0e0506716d06f4c4f0c771338dca0ef6a8d0e11d64e313636c)
BibTeX
@misc{dce81094fbeb14,
  title = {A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set — arXiv:2610.03131},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.03131},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e81094fbeb14; sha256 303c5ca07384cc0e0506716d06f4c4f0c771338dca0ef6a8d0e11d64e313636c},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.03131. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A set $S$ of vertices in a graph $G$ is a dominating set of $G$ if every vertex not in $S$ has a neighbor in $S$, where two vertices are neighbors if they are adjacent. The domination number, $\gamma(G)$, of $G$ is the minimum cardinality among all dominating sets of $G$. Given a set $S$ of vertices of a graph $G$, two vertices are located by $S$ if they have distinct sets of neighbors in $S$. Moreover, if $S$ locates every pair of vertices not in $S$, then it is called a locating set of $G$. A locating dominating set of $G$ is both a dominating and a locating set of $G$. The locating domination number, $\gamma^{\rm LD}(G)$, is the minimum cardinality among all locating dominating sets of $G$. A notable conjecture in the study of locating dominating sets is to show that the locating domination number of an isolate-free and twin-free graph of order $n$ is at most $\frac{1}{2}n$. So far, the best approximation to this upper bound conjecture is known to be $\left \lceil \frac{5}{8}n \right \rceil$. Much in line with the conjecture, an even stronger reformulation proposed in the literature asks if it is possible to partition the vertex set of an isolate-free and twin-free graph into two locating sets. However, such partitions into locating sets may not exist if the graph is also allowed to have twins. Continuing with this line of research, we show that if $G$ is an isolate-free (and not necessarily twin-free) graph, then the vertex set of $G$ can be partitioned into a dominating set and a locating dominating set. As a consequence, we infer that every isolate-free graph $G$ of order $n$ satisfies $\gamma(G) + \gamma^{\rm LD}(G) \le n$, and we show that the last bound is tight. Moreover, our proof of the existence of a partition of the vertex set of an isolate-free graph into a dominating and a locating dominating set also provides a polynomial-time algorithm to construct such a partition.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-05 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.03131 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T08:18:48.303Z dalla pagina https://arxiv.org/catchup/math.CO/2026-10-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).