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

Dipayan Chakraborty, Florent Foucaud, Michael Antony Henning, Tero Laihonen

► To cite this version:

Dipayan Chakraborty, Florent Foucaud, Michael Antony Henning, Tero Laihonen. A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set. 2025. hal-05022831

HAL Id: hal-05022831

https://hal.science/hal-05022831v1

Preprint submitted on 7 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
A note on partitioning the vertex set of a graph into
a dominating set and a locating dominating set

¹,²,³Dipayan Chakraborty, ¹Florent Foucaud, ²Michael A. Henning, and ⁴Tero Laihonen

¹ Université Clermont Auvergne, CNRS, Clermont Auvergne INP,
Mines Saint-Étienne, LIMOS, 63000 Clermont-Ferrand, France

Email: dipayan.chakraborty@uca.fr

Email: florent.foucaud@uca.fr

² Department of Mathematics and Applied Mathematics
University of Johannesburg, South Africa

Email: mahenning@uj.ac.za

³ Department of Computer Science and Mathematics
Lebanese American University, Beirut, Lebanon

⁴ Department of Mathematics and Statistics
University of Turku

Turku, FI-20014, Finland

Email: terolai@utu.fi

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, $\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^{\text{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 $G$ of order $n$ is at most $\left\lfloor \frac{1}{2}n \right\rfloor$. In a recent work [N. Bousquet, Q. Chuet, V. Falgas-Ravry, A. Jacques, and L. Morelle, A note on locating-dominating sets in twin-free graphs. Discrete Math. 348 (2025), 114297], the authors improve the best approximation to this conjectured $\left\lfloor \frac{5}{8}n \right\rfloor$-bound to $\left\lfloor \frac{5}{8}n \right\rfloor$ and further ask if the vertex set of an isolate-free and twin-free graph can be partitioned 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^{\text{LD}}(G) \le n$. Moreover, we show that the last bound is tight.
# 1 Introduction

Our aim is to show that if $G$ is an isolate-free graph, then the vertex set of $G$ can be partitioned into a dominating set and a locating dominating set. We begin with some basic definitions. Let $G$ be a graph with vertex set $V(G)$, edge set $E(G)$, and of order $n = |V(G)|$ and size $m(G) = |E(G)|$. Two vertices $u$ and $v$ of $G$ are adjacent if $uv \in E(G)$. Two adjacent vertices are called neighbors. The open neighborhood $N_G(v)$ of a vertex $v$ in $G$ is the set of neighbors of $v$, while the closed neighborhood of $v$ is the set $N_G[v] = \{v\} \cup N_G(v)$. For a set $S \subseteq V(G)$, its open neighborhood is the set $N_G(S) = \cup_{v \in S} N_G(v)$, and its closed neighborhood is the set $N_G[S] = N_G(S) \cup S$. Two vertices $u$ and $v$ are closed twins in $G$ if they have the same closed neighborhoods, that is, if $N_G[u] = N_G[v]$. The vertices $u$ and $v$ are open twins if they have the same open neighborhoods, that is, if $N_G(u) = N_G(v)$. A graph without closed or open twins is called twin-free.

The degree of a vertex $v$ in $G$ is the number of vertices adjacent to $v$ in $G$, and is denoted by $\deg_G(v)$, and so $\deg_G(v) = |N_G(v)|$. The maximum (minimum) degree among the vertices of $G$ is denoted by $\Delta(G)$ ($\delta(G)$, respectively). An isolated vertex in a graph $G$ is a vertex of degree zero. A graph without any isolated vertex is called an isolate-free graph. A leaf in $G$ is a vertex of degree 1 in $G$, and an edge incident with a leaf is a called a pendant edge. A support vertex is a vertex with at least one leaf neighbor. For a set $S \subseteq V(G)$, the subgraph induced by $S$ is denoted by $G[S]$. Further, the subgraph of $G$ obtained from $G$ by deleting all vertices in $S$ and all edges incident with vertices in $S$ is denoted by $G-S$; that is, $G-S = G[V(G) \setminus S]$. We use $P_n$, $C_n$, and $K_n$ to denote a path, a cycle, and a complete graph, respectively, on $n$ vertices. For $1 \le r \le s$, we denote a complete bipartite graph with partite sets of cardinalities $r$ and $s$, respectively, by $K_{r,s}$. A star is a complete bipartite graph $K_{1,s}$ for some $s \ge 1$.

A set $S \subseteq V(G)$ is a dominating set of a graph $G$ if every vertex in $V(G) \setminus S$ has at least one neighbor in $S$. Thus, a set $S$ is a dominating set of $G$ if every vertex in $V(G) \setminus S$ is adjacent to at least one vertex in $S$. Equivalently, $S$ is a dominating set of $G$ if $N_G[v] \cap S \ne \emptyset$ for all vertices $v$ of $G$. A vertex $v$ in $G$ dominates itself and all its neighbors. The domination number $\gamma(G)$ is the minimum cardinality among all dominating set in $G$. A dominating vertex in $G$ is a vertex $v$ adjacent to every other vertex of $G$. A total dominating set of an isolate-free graph $G$ is a dominating set $S$ with the property that $G[S]$ is isolate-free, that is, $N_G(v) \cap S \ne \emptyset$ for all vertices $v$ of $G$. A dominating set $S$ is an independent dominating set of $G$ if $S$ is an independent set in $G$, that is, $G[S]$ consists of isolated vertices. We refer to the books [20, 21, 22, 31] for a detailed study of domination and its variants.

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$. If $S$ locates each pair of distinct vertices in $V(G) \setminus S$, then $S$ is called a locating set of $G$. A locating dominating set of $G$, abbreviated LD-set, is a dominating set $S$ of $G$ with the additional property that every two vertices not in $S$ are located by $S$. Hence an LD-set is a vertex subset $S$ of $G$ such that $S$ is a dominating set of $G$ and $N_G(u) \cap S \ne N_G(v) \cap S$ for all distinct vertices $u, v \in V(G) \setminus S$. Thus, every two vertices outside the dominating set $S$
are located by the set $S$. The *locating domination number*, $\gamma^{LD}(G)$, is the minimum cardinality among all LD-sets of $G$. The concept of an LD-set was introduced by Slater in the 1980s [35], who first coined the concept *locating dominating set*. We remark that a locating dominating set is also called a locating dominating code in the literature. We refer the reader to the excellent survey article on locating dominating sets in graphs by Lobstein, Hudry, and Charon [33]. Locating dominating sets are now very well studied in the literature (see, [3, 6, 8, 9] for a small sample of recent papers on the topic).

**1.1 Motivation**

The following classic 1962 result by Ore showed that for any isolate-free graph, its vertex set can be partitioned into two dominating sets.

**Theorem 1** ([34]) *If $G$ is an isolate-free graph of order $n$ and $S$ is a minimal dominating set of $G$, then $V(G) \setminus S$ is a dominating set, and thus $\gamma(G) \le \frac{1}{2}n$.*

Ore's result that the vertex set of graph can be partitioned into two dominating sets does not necessarily extend to other types of domination parameters. For example, the vertices of a 5-cycle cannot be partitioned into a dominating set and a total dominating set. However it is shown in [29] that if $G$ is a connected graph with minimum degree at least 2 and $G$ is not the 5-cycle, then the vertex set of $G$ can be partitioned into a dominating set and a total dominating set. Hence, a natural problem is to consider which graphs can be partitioned into two specific types of dominating sets. Such problems have been studied in [2, 4, 5, 12, 13, 19, 23, 24, 25, 26, 27, 28, 29, 30, 32, 36, 37] and elsewhere.

Much of the interest in locating dominating sets is the $\frac{1}{2}n$-upper bound conjecture on the locating domination number of twin-free and isolate-free graphs by Garijo, González, and Márquez [14] in 2014, with a slightly stronger reformulation by Foucaud and Henning in [16].

**Conjecture 1** ([14, 16]) *If $G$ is an isolate-free, twin-free graph of order $n$, then $\gamma^{LD}(G) \le \frac{1}{2}n$.*

Conjecture 1 is known to hold for special classes of graphs, including graphs without 4-cycles [14], graphs of girth at least 5 and minimum degree at least 2 [1], split graphs and co-bipartite graphs [18], line graphs [17], maximal outerplanar graphs [11], block graphs [9] and cubic graphs [16] with the latter being generalized to subcubic graphs [10]. As a motivation to prove Conjecture 1, several authors have considered the following problem which has a slightly stronger formulation.

**Problem 1** ([14, 15, 18]) *Determine classes of isolate-free, twin-free graphs $G$ with the property that $V(G)$ can be partitioned into two locating dominating sets.*

Notice that determining the graph class in Problem 1 to be “all isolate-free and twin-free graphs” necessarily proves Conjecture 1. For example, the vertex set of an isolate-free and twin-free bipartite graph can be partitioned into two locating dominating sets [14]. It has also
been shown in [9] that the class of isolate-free and twin-free block graphs can be partitioned
into two locating dominating sets.

However, as a preliminary investigation, it is not yet known to the authors if there exist
examples of isolate-free and twin-free graphs whose vertex sets cannot be partitioned into two
locating dominating sets (notice that finding such an example does not, however, disprove
Conjecture 1 as long as a minimum locating dominating set of the example has cardinality at
most $\frac{1}{2}n$). In a recent paper by Bousquet et al. [3] where the best-known approximation to the
$\frac{1}{2}n$-upper bound conjecture has been improved to $\lceil \frac{5}{8}n \rceil$, the authors also ask a more general
version of the question in Problem 1 that effectively translates to asking the following.

**Problem 2 ([3]**)) *Given an isolate-free and twin-free graph G, can its vertex set be partitioned into two locating sets?*

Notice that any graph which satisfies Problem 1 automatically also satisfies Problem 2, since
a locating dominating set is also, by definition, a locating set (and moreover, one can obtain a
locating dominating set from any locating set by adding at most one vertex to the latter set).
Thus, any isolate-free and twin-free graph from either the class of block graphs or bipartite
graphs satisfies Problem 2. Moreover, it is not too difficult to verify that, for example, the
vertex set of a graph from the class of isolate-free and twin-free either cobipartite or split
graphs can be partitioned into its two canonical parts (which are either cliques or independent
sets) each of which serves as a locating set. Notice that answering Problem 2 will imply
$\gamma^{\text{LD}}(G) \le \lceil \frac{1}{2}(n+1) \rceil$ for any general isolate-free and twin-free graph G, which too would bring
us quite close to proving Conjecture 1.

Thus, in this line of research as prescribed in both Problems 1 and 2, given an isolate-free
and twin-free graph G, the objective is to maximize the sum-total of the “locating (dominating)
power” of vertex subset A ⊂ V(G) on its complement V(G) \ A and vice-versa. However, such
questions need to be slightly modified when we allow the graphs to contain twins. For example,
if $G \cong K_{1,n-1}$ (which contains open twins), then it is certainly not possible to partition the
vertex set of G into two locating dominating (or locating) sets since any locating (dominating)
set of G requires at least all-but-one of its leaves and thus, its complement cannot be a locating
(dominating) set. Similar is the story for $G \cong K_n$ (which contains closed twins). In both these
examples, however, it is possible to partition the vertex set into a dominating set (consisting
of a single dominating vertex of G) and a locating dominating set (the complement of the
dominating set). Therefore, this motivates us to consider the following question on isolate-free
(and not necessarily twin-free) graphs.

**Problem 3** *Can an isolate-free graph be partitioned into a dominating and a locating domi-
nating set?*

In this paper, we answer Problem 3 positively. This also immediately implies that for any
isolate-free graph G of order n, we have $\gamma^{\text{LD}}(G) \le n - \gamma(G)$. Hence, the partition proposed in
Problem 3 may be considered as a generalization of the $\frac{1}{2}n$-upper bound in Conjecture 1 for
isolate-free graphs which are allowed to have twins. Moreover, this $(n - \gamma(G))$-upper bound is
tight since, considering the same examples as before, for any graph $G \cong K_{1,n-1}$ or $G \cong K_n$, we
have $\gamma(G) = 1$ and $\gamma^{\text{LD}}(G) = n - 1$.
A similar result for identifying codes<fnref n="1" /> has been established by Chakraborty et al. in [7], where it has been shown that $\gamma(T) + \gamma^{\text{ID}}(T) \le n$ for all trees of order $n$ except when $T \cong P_4$. Since it is not too difficult to see that an identifying code of a graph $G$ is also a locating dominating set of $G$, it can be inferred that $\gamma(T) + \gamma^{\text{LD}}(T) \le n$ as well for all trees (also when $T \cong P_4$ by simply considering one set containing the two leaves and the other set being its complement). However, our work in this paper proves that the last inequality holds for all isolate-free graphs.

## 2 Main results

In this paper we study graphs whose vertex set can be partitioned into a dominating set and a locating dominating set. We refer to such a partition of the vertices of a graph $G$ as a DLDS-partition of $G$ (standing for “dominating, locating dominating set partition”). If $G$ has a DLDS-partition, then we say that $G$ is a DLDS-graph, standing for “dominating, locating dominating set graph.” We shall prove the following result which shows that the vertex set of every isolate-free graph has a DLDS-partition.

**Theorem 2** Every isolate-free graph is a DLDS-graph.

As an immediate consequence of Theorem 2, we infer the following result.

**Corollary 1** If $G$ is an isolate-free graph of order $n$, then $\gamma(G) + \gamma^{\text{LD}}(G) \le n$.

We again remark that the bound in Corollary 1 is tight. Apart from stars $K_{1,n-1}$ and complete graphs $K_n$, another simple example is to take the corona of a graph, where the corona $G = H \circ K_1$ of a connected graph $H$ is the graph obtained from $H$ by adding for each vertex $v \in V(H)$ a new vertex $v'$ and the edge $vv'$. In this case, if $D$ is the set of all vertices added to $H$ when constructing $G$, then the partition $\{D, V(H)\}$ is an example of a DLDS-partition of $V(G)$ into a dominating set $D$ and a locating dominating set $V(H)$. In this example, if $G$ has order $n$, then $\gamma(G) = \gamma^{\text{LD}}(G) = \frac{1}{2}n$, and so $\gamma(G) + \gamma^{\text{LD}}(G) = n$. For example, the corona $G = C_5 \circ K_1$ of a 5-cycle is illustrated in Figure 1, where the set $D$ is indicated by the white vertices and the locating dominating set by the shaded vertices. (We remark that the DLDS-partition in this example is not unique.)

<figure><img src="image_2.png" /><figcaption>Figure 1: A DLDS-partition of the corona $G = C_5 \circ K_1$ of a 5-cycle</figcaption></figure>

<footnote n="1">¹an identifying code $D$ of a graph $G$ is one which is a dominating set of $G$ and has the extra condition that $N_G[u] \cap D \neq N_G[v] \cap D$ for all distinct $u, v \in V(G)$. Identifying codes exist only when the graph has no closed twins. The identification number of a graph $G$, denoted $\gamma^{\text{ID}}(G)$, is the smallest cardinality among all identifying codes of $G$</footnote>
### 3 Proof of Theorem 2

We proceed by induction on the order $n$ of an isolate-free graph $G$ to show that $G$ is a DLDS-graph. If $n=2$, then $G = K_2$ and trivially $G$ has a DLDS-partition (where we add one of the vertices to the dominating set $D$ and the other vertex to the locating dominating set $L$, as illustrated in Figure 2(a)). If $n=3$, then either $G = P_3$ or $G = K_3$. In both cases, the graph $G$ is a DLDS-graph, as illustrated in Figure 2(b) and 2(c) where the shaded vertices form a locating dominating set $L$ and the white vertices a dominating set $D$ resulting in a DLDS-partition $\{D, L\}$. This establishes the base cases. Let $n \ge 4$ and assume that every isolate-free graph of order less than $n$ is a DLDS-graph.

<figure><img src="image_3.png" /><figcaption>Figure 2: DLDS-partitions of graphs of small order</figcaption></figure>

We note that an isolate-free graph is a DLDS-graph if and only if every component of the graph is a DLDS-graph. If $G$ is disconnected, then applying the inductive hypothesis to every component of $G$ we infer that $G$ is a DLDS-graph. Hence we may assume that $G$ is connected. We proceed further with the following series of claims that establish structural properties of the graph $G$.

**Claim 1** If $G$ has a dominating vertex, then $G$ is a DLDS-graph.

**Proof.** Suppose that $G$ has a dominating vertex $v$, and so $\deg_G(v) = n-1$. In this case, we let $D = \{v\}$ be the singleton set consisting of the dominating vertex $v$ and we let $L = V(G) \setminus \{v\}$. The resulting set $\{D, L\}$ is a DLDS-partition of $G$, implying that $G$ is a DLDS-graph.

By Claim 1, we may assume that $G$ has no dominating vertex, for otherwise $G$ is a DLDS-graph as desired. Thus, $\Delta(G) \le n-2$. With this assumption, if $n=4$, then $G = P_4$ or $G = C_4$. In both cases, we let $D$ be a set consisting of two adjacent vertices of degree 2 and we let $L$ denote the remaining two vertices of $G$ as illustrated in Figure 2(d) and 2(e). The resulting set $\{D, L\}$ is a DLDS-partition of $G$. (We remark that the DLDS-partition in the above examples are not necessarily unique.) Hence, we may assume that $n \ge 5$, for otherwise the desired result is immediate.

**Claim 2** If $\delta(G) = 1$, then $G$ is a DLDS-graph.

**Proof.** Suppose that $\delta(G) = 1$. Let $v$ be a support vertex of $G$, and let $L_v$ be the set of leaf neighbors of $v$ in $G$. We now consider the graph $G' = G - (L_v \cup \{v\})$. By our earlier assumptions, the graph $G$ has no dominating vertex. The graph $G'$ is therefore an isolate-free graph. Applying the inductive hypothesis to $G'$, there is a DLDS-partition $\{D', L'\}$ of $V(G')$
into a dominating set $D'$ and a locating dominating set $L'$ of $G'$. Letting $D = D' \cup \{v\}$ and $L = L' \cup L_v$, we infer that $\{D, L\}$ is a DLDS-partition of $G$, noting that the vertex $v \in D$ is located by the subset $L_v \subset L$.

By Claim 2, we may assume that $\delta(G) \ge 2$, for otherwise $G$ is a DLDS-graph, as desired.

**Claim 3** If $G$ has open twins, then $G$ is a DLDS-graph.

**Proof.** Suppose that $G$ has open twins, and consider a set $X$ of (mutual) open twins in $G$ where each vertex in $X$ has the same open neighborhood, say $Y$. Thus the set $X$ is an independent set, $|X| \ge 2$, and $N_G(x) = Y$ for every vertex $x \in X$. Let $|X| = r \ge 2$ and let $|Y| = s$. Since $\delta(G) \ge 2$, we note that $s \ge 2$. Let $x$ be an arbitrary vertex in $X$ and let $y$ be an arbitrary vertex in $Y$.

We now consider the graph $G' = G - \{x, y\}$. If $G'$ contains an isolated vertex $v$, then since the edges between $X$ and $Y$ in $G$ induce a complete bipartite graph $K_{r,s}$ where $r, s \ge 2$, we infer that $v$ is a vertex of degree 1 in $G$ with $y$ as its unique neighbor, contradicting our earlier assumption that $\delta(G) \ge 2$. Hence, $G'$ is an isolate-free graph. Applying the inductive hypothesis to the isolate-free graph $G'$, there is a DLDS-partition $\{D', L'\}$ of $V(G')$ into a dominating set $D'$ and a locating dominating set $L'$ of $G'$.

Let $X' = X \setminus \{x\}$ and let $Y' = Y \setminus \{y\}$. If $D' \cap X' \ne \emptyset$ and $D' \cap Y' \ne \emptyset$, then letting $D = D'$ and $L = L' \cup \{x, y\}$, we infer that $\{D, L\}$ is a DLDS-partition of $G$. Hence we may assume that $D' \cap X' = \emptyset$ or $D' \cap Y' = \emptyset$. Suppose that $D' \cap Y' = \emptyset$, and so $Y' \subseteq L'$. Since $D'$ is a dominating set of $G'$ and $X'$ is an independent set, in order to dominate the vertices in $X'$ we note that $X' \subseteq D'$. In this case, letting $D = D' \cup \{y\}$ and $L = L' \cup \{x\}$, we infer that $\{D, L\}$ is a DLDS-partition of $G$ noting that the vertex $x \in L$ locates the vertex $y \in D$ since $y$ is the only vertex in $D$ that is adjacent to $x$.

Hence, we may assume that $D' \cap X' = \emptyset$, for otherwise the desired result holds. Thus, $X' \subseteq L'$. Since $D'$ is a dominating set of $G'$, in order to dominate the vertices in $X'$ we note that $D' \cap Y' \ne \emptyset$. In particular, we note that the vertex $x$ is adjacent in $G$ to a vertex of $D'$. Suppose that $y$ is adjacent in $G$ to at least one vertex that belongs to the set $D'$. In this case, we let $D = D'$ and $L = L' \cup \{x, y\}$. The resulting partition $\{D, L\}$ is a DLDS-partition of $G$, yielding the desired result.

Hence we may assume that $y$ is adjacent in $G$ to no vertex that belongs to the set $D'$, that is, all neighbors of $y$ in $G$ different from $x$ belong to the set $L'$. In this case, we let $D = D' \cup \{x\}$ and $L = L' \cup \{y\}$. We note that all vertices in $D'$ are located by the set $L'$. Further, each vertex in $D' \cap Y'$ is adjacent to all vertices in $X'$, where recall that $X' \subseteq L'$. Since the vertex $y \in L$ has no neighbor in the set $D$ except for the vertex $x$, the vertex $x \in D$ is located by the vertex $y \in L$ in the set $L$. We therefore infer that the partition $\{D, L\}$ is a DLDS-partition of $G$, once again yielding the desired result that $G$ is a DLDS-graph.

Notice that the previous proof gives us a way to find a desired partition when there are open twins in a graph which play a special role in locating dominating sets. By Claim 3, we may also assume that $G$ has no open twins, for otherwise $G$ is a DLDS-graph as desired. Let $C$ be a maximal clique in $G$, and so $C$ is a set of vertices in $G$ that induce a complete graph and no superset of $C$ is a clique. By our earlier assumption, the graph $G$ has no dominating vertex, implying that $C \ne V(G)$. Let $I$ be the set of isolated vertices in $G-C$. Since $G$ is isolate-free,
we note that every vertex in $I$ has all its neighbors in $C$, that is, $N_G(u) \subseteq C$ for all $u \in I$. Moreover since $G$ has no open twins, we note that if $u$ and $v$ are two distinct vertices in $I$, then $N_G(u) \cap C \neq N_G(v) \cap C$.

**Claim 4** If $V(G) = C \cup I$, then $G$ is a DLDS-graph.

**Proof.** Suppose that $V(G) = C \cup I$. Let $D$ be a subset of vertices in the clique $C$ of minimum cardinality that dominates the set $I$. Thus, every vertex in $I$ is adjacent in $G$ to at least one vertex in $D$ and no proper subset of $D$ dominates the set $I$ in the graph $G$. Since $G$ has no dominating vertex, we infer that $|D| \geq 2$. By our choice of the set $D$, if $v$ is an arbitrary vertex in $D$, then $D \setminus \{v\}$ does not dominate the set $I$, implying that there is at least one vertex $v' \in I$ such that $N_G(v') \cap D = \{v\}$. Letting $L = V(G) \setminus D$, the partition $\{D, L\}$ is a DLDS-partition of $G$ by our earlier observation that each vertex in $D$ dominates at least one vertex in $I \subseteq L$ that is not dominated by any other vertex of $D$, yielding the desired result.

By Claim 4, we may assume that $C \cup I$ is a proper subset of $V(G)$, for otherwise $G$ is a DLDS-graph as desired. We now consider the graph $G' = G - (C \cup I)$. By definition of the set $I$ we note that the graph $G'$ is isolate-free. Applying the inductive hypothesis to $G'$, there is a DLDS-partition $\{D', L'\}$ of $V(G')$ into a dominating set $D'$ and a locating dominating set $L'$ of $G'$.

**Claim 5** If $I \neq \emptyset$, then $G$ is a DLDS-graph.

**Proof.** Suppose that $I \neq \emptyset$. Let $D_C$ be a subset of vertices in the clique $C$ of minimum cardinality that dominates the set $I$ in $G$. We note that possibly $|D_C| = 1$. We now let $D = D' \cup D_C$ and we let $L = V(G) \setminus D$. We note that $L' \subset L$ and $I \subset L$. Further, we note as in the proof of Claim 4 that by the minimality of the set $D_C$, each vertex in $D_C$ dominates at least one vertex in $I$ that is not dominated by any other vertex of $D_C$. Thus, every vertex in $D_C$ is located by the set $L$. We therefore infer that the partition $\{D, L\}$ is a DLDS-partition of $G$, yielding the desired result.

By Claim 5, we may assume that $I = \emptyset$, for otherwise $G$ is a DLDS-graph as desired. Suppose that every vertex in the clique $C$ is adjacent in $G$ to at least one vertex that belongs to the set $D'$. In this case, we let $D = D'$ and $L = L' \cup C$, and we infer that $\{D, L\}$ is a DLDS-partition of $G$. Hence we may assume that at least one vertex, say $v$, in the clique $C$ has no neighbor in $G$ that belongs to the set $D'$. Thus, $N_G(v) \cap V(G') \subseteq L'$. Let $w$ be an arbitrary vertex in $C \setminus \{v\}$, and let $D = D' \cup \{w\}$ and $L = (L' \cup C) \setminus \{w\}$. In particular, we note that $v \in L$ and every neighbor of $v$ in $G$ belongs to the set $L$, except for the vertex $w$. The vertex $w$ is therefore located by the vertex $v \in L$, and we infer that the partition $\{D, L\}$ is a DLDS-partition of $G$. This completes the proof of Theorem 2.

## Acknowledgements

This research was supported by the French government IDEX-ISITE initiative 16-IDEX-0001 (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 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 Academy of Finland grant number 338797.

## References

[1] C. Balbuena, F. Foucaud and A. Hansberg, Locating-Dominating Sets and Identifying Codes in Graphs of Girth at least 5. Electron. J. Comb. **22**(2) (2015), P2.15.

[2] D. W. Bange, A. E. Barkauskas, and P. J. Slater, Disjoint dominating sets in trees. Sandia Laboratories Rept. SAND-78-1087J, 1978.

[3] N. Bousquet, Q. Chuet, V. Falgas-Ravry, A. Jacques, and L. Morelle, A note on locating-dominating sets in twin-free graphs. *Discrete Math.* **348** (2025), No. 2, Paper No. 114297, 5 pp.

[4] I. Broere, M. Dorfling, W. Goddard, J. H. Hattingh, M. A. Henning, and E. Ungerer, Augmenting trees to have two disjoint total dominating sets. *Bull. Inst. Combin. Appl.*

[5] P. Delgado, W. J. Desormeaux, and T. W. Haynes, Partitioning the vertices of a graph into a total dominating set and an independent dominating set. *Ars Combin.* **144** (2019), 367–379.

[6] D. Chakraborty, F. Foucaud, A. Hakanen, M. A. Henning, and A. K. Wagler, Progress towards the two-thirds conjecture on locating-total dominating sets. *Discrete Math.* **347** (2024), No. 12, Paper No. 114176, 14 pp.

[7] D. Chakraborty, F. Foucaud, M.A. Henning and T. Lehtilä, Identifying codes in graphs of given maximum degree: Characterizing trees. *arXiv:2403.13172 [math.CO]* (2024).

[8] D. Chakraborty, F. Foucaud, and T. Lehtilä, Identifying codes in bipartite graphs of given maximum degree. *Procedia Comput. Sci.* **223** (2023), 157–165.

[9] D. Chakraborty, F. Foucaud, A. Parreau, and A. K. Wagler, On three domination-based identification problems in block graphs. *Fund. Inform.* **191** (2024), No. 3-4, 197–229.

[10] D. Chakraborty, A. Hakanen, T. Lehtilä, T. The n/2-bound for locating-dominating sets in subcubic graphs. *arXiv:2406.19278 [math.CO]* (2024).

[11] M. Claverol, A. García, G. Hernández, C. Hernando, M. Maureso, M. Mora, J. Tejel, Metric dimension of maximal outerplanar graphs. *Bull. Malays. Math. Sci. Soc.* **44** (2021), pp. 2603-2630.

[12] W. J. Desormeaux, T. W. Haynes, and M. A. Henning, Partitioning the vertices of a cubic graph into two total dominating sets. *Discrete Appl. Math.* **223** (2017), 52–63.

[13] M. Dorfling, W. Goddard, J. H. Hattingh, and M. A. Henning, Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets. *Discrete Math.* **300** (2005), 82–90.
[14] D. Garijo, A. González, and A. Márquez, The difference between the metric dimension and the determining number of a graph. *Appl. Math. Comput.* **249** (2014), 487–501.

[15] F. Foucaud and M. A. Henning, Locating-total dominating sets in twin-free graphs: a conjecture. *Electron. J. Combin.* **23** (2016), No. 3, Paper 3.9, 18 pp.

[16] F. Foucaud and M. A. Henning, Location-domination and matching in cubic graphs. *Discrete Math.* **339** (2016), No. 4, 1221–1231.

[17] F. Foucaud and M.A. Henning, Location-domination in line graphs. Discrete Math. **340** (2017), pp. 3140-3153.

[18] F. Foucaud, M.A. Henning, C. Löwenstein, T. Sasse, Locating-dominating sets in twin-free graphs. Discret. Appl. Math. **200** (2016), pp. 52-58.

[19] W. Goddard and M. A. Henning, Thoroughly dispersed colorings. *J. Graph Theory* **88** (2018), 174–191.

[20] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning (eds), *Topics in Domination in Graphs*. Series: Developments in Mathematics, Vol. 64, Springer, Cham, 2020. viii + 545 pp.

[21] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning (eds), *Structures of Domination in Graphs*. Series: Developments in Mathematics, Vol. 66, Springer, Cham, 2021. viii + 536 pp.

[22] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, *Domination in Graphs: Core Concepts* Series: Springer Monographs in Mathematics, Springer, Cham, 2023. xx + 644 pp.

[23] T. W. Haynes and M. A. Henning, Graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set. *Opuscula Math.* **44** (2024), no. 4, 543–563.

[24] T. W. Haynes and M. A. Henning, A characterization of graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set. *Discrete Appl. Math.* **358** (2024), 457–467.

[25] P. Heggernes and J. A. Telle, Partitioning graphs into generalized dominating sets. *Nordic J. Comput.* **5** (1998), 128–142.

[26] M. A. Henning, C. Löwenstein, and D. Rautenbach, Partitioning a graph into a dominating set, a total dominating set, and something else. *Discuss. Math. Graph Theory* **30** (2010), no. 4, 563–574.

[27] M. A. Henning, C. Löwenstein, D. Rautenbach, and J. Southey, Disjoint dominating and total dominating sets in graphs. *Discrete Appl. Math.* **158** (2010), 1615–1623.

[28] M. A. Henning and I. Peterin, A characterization of graphs with disjoint total dominating sets. *Ars Math. Contemp.* **16** (2019), no. 2, 359–375.
[29] M.A. Henning and J. Southey, A note on graphs with disjoint dominating and total dominating sets. *Ars Combin.* **89** (2008), 159-162.

[30] M. A. Henning and J. Southey, A characterization of graphs with disjoint dominating and total dominating sets. *Quaest. Math.* **32** (2009), no. 1, 119–129.

[31] M. A. Henning and A. Yeo, *Total domination in graphs*. Series: Springer Monographs in Mathematics, Springer, Cham, New York, 2013. xiv + 178 pp.

[32] M. A. Henning and A. Yeo, Graphs with disjoint total dominating sets. *Total Domination in Graphs* (Springer Monographs in Mathematics) (2013), 119–124.

[33] A. Lobstein, O. Hudry, and I. Charon, Locating-domination and identification. *Topics in Domination in Graphs*, Dev. Math. **64** Springer, Cham, (2020), 251–299.

[34] O. Ore, *Theory of Graphs*, Amer. Math. Soc. Colloq. Pub., Providence, RI. **38** (1962).

[35] P. J. Slater. Dominating and reference sets in graphs. *J. Math. Phys. Sci.* **22** (1988), no. 4, 445–455.

[36] J. Southey, *Domination Results: Vertex Partitions and Edge Weight Functions*. PhD Thesis, Univ. Johannesburg, May 2012.

[37] J. Southey and M. A. Henning, Dominating and total dominating partitions in cubic graphs. *Cent. Eur. J. Math.* **9** (2011), no. 3, 699–708.