A1 Refereed original research article in a scientific journal

A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set




AuthorsChakraborty, Dipayan; Foucaud, Florent; Henning, Michael A.; Laihonen, Tero

PublisherElectronic Journal of Combinatorics

Publication year2026

Journal: The Electronic Journal of Combinatorics

Article number51

Volume33

Issue1

ISSN1097-1440

eISSN1077-8926

DOIhttps://doi.org/10.37236/14049

Publication's open availability at the time of reportingOpen Access

Publication channel's open availability Open Access publication channel

Web address https://doi.org/10.37236/14049

Self-archived copy’s web addresshttps://research.utu.fi/converis/portal/detail/Publication/523504067

Self-archived copy's licenceCC BY

Self-archived copy's versionPublisher`s PDF


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, 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 G of order n is at most ½n. So far, the best approximation to this ½n-upper bound conjecture is known to be 5/8n⌉ . In fact, much in line with the conjecture, an even stronger reformulation proposed in the literature is to ask 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≤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.


Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.




Funding information in the publication
This research was supported by the French government IDEX-ISITE initiative 16-IDEX0001 (CAP 20-25), International Research Center “Innovation Transportation and Production Systems” of the I-SITE CAP 20-25, by the ANR project GRALMECO (ANR-21- CE48-0004). The research of Dipayan Chakraborty was additionally supported in part by the Lebanese American University under the President’s Intramural Research Fund PIRF0056. The research of Michael A. Henning was supported in part by the South African National Research Foundation (grants 132588) and the University of Johannesburg. Research of Tero Laihonen was partially supported by the Research Council of Finland grant number 338797. In addition, we thank the anonymous referees for their helpful comments and insightful suggestions, which were valuable additions to this paper.


Last updated on 22/05/2026 01:43:13 PM