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

Abstract

<p> A set <span>S</span> of vertices in a graph <span>G</span> is a dominating set of <span>G</span> if every vertex not in <span>S</span> has a neighbor in <span>S</span>, where two vertices are neighbors if they are adjacent. The domination number, <span>γ(G)</span>, of <span>G</span> is the minimum cardinality among all dominating sets of <span>G</span>. Given a set <span>S</span> of vertices of a graph <span>G</span>, two vertices are located by <span>S</span> if they have distinct sets of neighbors in <span>S</span>. Moreover, if <span>S</span> locates every pair of vertices not in <span>S</span>, then it is called a locating set of <span>G</span>. A locating dominating set of <span>G</span> is both a dominating and a locating set of <span>G</span>. The locating domination number, <span>γ<span>^LD</span></span>, is the minimum cardinality among all locating dominating sets of <span>G</span>. 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 <span>G</span> of order <span>n</span> is at most ½<span>n</span>. So far, the best approximation to this ½<span>n</span>-upper bound conjecture is known to be <span>⌈<span>5</span><span>/8</span>n⌉</span> . 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 <span>G</span> is an isolate-free (and not necessarily twin-free) graph, then the vertex set of <span>G</span> can be partitioned into a dominating set and a locating dominating set. As a consequence, we infer that every isolate-free graph <span>G</span> of order~<span>n</span> satisfies <span>γ(G)+γ<span>^LD</span>≤n</span>, 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. <br></p>