A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set
Abstract
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, γ(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, γ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 1/2n. So far, the best approximation to this upper bound conjecture is known to be ⌈ 5/8n ⌉. 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 γ(G) + γLD(G) ≤ 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.
Versions
Related
- Every cubic graph has four total dominating sets covering each vertex at most twice
- Optimal (1,≤ ℓ)-locating-dominating codes in infinite triangular grid
- Locating a Seymour vertex in oriented graphs having minimum outdegree at most 7
- Partitioning an S-packing coloring into broadcast dominating sets
- Vertices that belong to every minimum dominating set of a graph and their connection with transportation sharing systems with study cases in Campo de Gibraltar area
BibTeX
@misc{chakraborty2026note,
title = {{A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set}},
author = {Dipayan Chakraborty and Florent Foucaud and Michael A. Henning and Tero Laihonen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03131},
eprint = {2610.03131},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03131},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set
AU - Dipayan Chakraborty
AU - Florent Foucaud
AU - Michael A. Henning
AU - Tero Laihonen
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03131
UR - https://arxiv.org/abs/2610.03131
AB - 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, γ(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, γ^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 1/2n. So far, the best approximation to this upper bound conjecture is known to be ⌈ 5/8n ⌉. 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 γ(G) + γ^LD(G) ≤ 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.
ER -