# Locating-dominating partitions for some classes of graphs

Florent Foucaud, Paras Vinubhai Maniya, Kaustav Paul, Dinabandhu Pradhan

► To cite this version:

Florent Foucaud, Paras Vinubhai Maniya, Kaustav Paul, Dinabandhu Pradhan. Locating-dominating partitions for some classes of graphs. Discrete Mathematics, 2026, 349 (3), pp.114886. 10.1016/j.disc.2025.114886. hal-05383647

HAL Id: hal-05383647

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

Submitted on 26 Nov 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
Locating-dominating partitions for some classes of graphs

Florent Foucaud$^a$, Paras Vinubhai Maniya$^b$, Kaustav Paul$^c$, Dinabandhu Pradhan$^{b,*}$

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

$^b$Department of Mathematics & Computing, Indian Institute of Technology (ISM) Dhanbad, 826004, Jharkhand, India

$^c$Department of Mathematics, Indian Institute of Technology Ropar, Rupnagar, 140001, Punjab, India

**Abstract**

A dominating set of a graph $G$ is a set $D \subseteq V(G)$ such that every vertex in $V(G) \setminus D$ is adjacent to at least one vertex in $D$. A set $L \subseteq V(G)$ is a locating set of $G$ if every two vertices in $V(G) \setminus L$ have pairwise distinct open neighborhoods in $L$. A set $D \subseteq V(G)$ is a locating-dominating set of $G$ if $D$ is a dominating set and a locating set of $G$. The location-domination number of $G$, denoted by $\gamma_{LD}(G)$, is the minimum cardinality among all locating-dominating sets of $G$. A well-known conjecture in the study of locating-dominating sets is that if $G$ is an isolate-free and twin-free graph of order $n$, then $\gamma_{LD}(G) \le \frac{n}{2}$. Recently, Bousquet et al. [Discrete Math. 348 (2025), 114297] proved that if $G$ is an isolate-free and twin-free graph of order $n$, then $\gamma_{LD}(G) \le \lfloor \frac{5n}{8} \rfloor$ and posed the question whether the vertex set of such a graph can be partitioned into two locating sets. We answer this question affirmatively for twin-free distance-hereditary graphs, maximal outerplanar graphs, split graphs, and co-bipartite graphs. In fact, we prove a stronger result: for any graph $G$ without isolated vertices and twin vertices, if $G$ is a distance-hereditary graph or a maximal outerplanar graph or a split graph or a co-bipartite graph, then the vertex set of $G$ can be partitioned into two locating-dominating sets. Consequently, this also confirms the original conjecture for these graph classes.

**Keywords:** Domination number, location-domination number, LD-partition, distance-hereditary graphs, maximal outerplanar graphs, split graphs.

**1. Introduction**

All the graphs considered in this paper are finite, simple, and undirected. For a graph $G$, we use $V(G)$ and $E(G)$ to denote the vertex set and the edge set of $G$, respectively. Two vertices $u$ and $v$ of $G$ are adjacent if $uv \in E(G)$. The neighbors of $v$ in $G$ are the vertices adjacent to $v$ in $G$. 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)$. 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)$. An isolated vertex in a graph $G$ is a vertex of degree 0. A graph without any isolated vertex is called an *isolate-free graph*. A vertex of degree 1 in $G$ is a *leaf* of $G$. The *maximum degree* of $G$ is the value $\max\{\deg_G(v): v \in V(G)\}$. For vertices $u$ and $v$, $u$ and $v$ are called *false* (respectively, *true*) twins in $G$ if $N_G(u) = N_G(v)$ (respectively, $N_G[u] = N_G[v]$). Further, $u$ and $v$ are *twins* in $G$ if they are false twins or true twins in $G$. A graph is *twin-free* if it does not contain twins. In a rooted tree, one vertex is designated as the root. Consider a tree $T$ with the vertex $r$ as the root. For each vertex $v \ne r$ of $T$, the *parent* of $v$ in $T$ is the neighbor of $v$ on the unique path from the root $r$ to $v$ in $T$. A *child* of $v$ in $T$ is any of its neighbors other than its parent.

<footnote>*Corresponding author</footnote>

<footnote>Email addresses: florent.foucaud@uca.fr (Florent Foucaud), maniyaparas9999@gmail.com (Paras Vinubhai Maniya), kaustav.20maz0010@iitrpr.ac.in (Kaustav Paul), dina@iitism.ac.in (Dinabandhu Pradhan)</footnote>
In this paper, we study distance-hereditary graphs, maximal outerplanar graphs, split graphs, and co-bipartite graphs. A *distance-hereditary graph* is a graph in which the distance between any two vertices in any connected induced subgraph is the same as in the original graph. Their structure allows them to be built up recursively, which makes them useful for studying certain domination parameters (see [4, 17, 19]). Similarly, maximal outerplanar graphs, abbreviated as mops form a fundamental subclass of planar graphs. A graph is a *mop* if it can be embedded in the plane such that all vertices lie on the boundary of its outer face (unbounded face) and all interior faces are triangles. Their well-understood structure allows for detailed combinatorial analysis, and they have been extensively studied in the context of domination parameters (see [1, 2, 10–12]). The set $X \subseteq V(G)$ is called a *clique* (*independent set*) of $G$ if every pair of vertices of $X$ are adjacent (nonadjacent) in $G$. A graph is a *split graph* if its vertex set can be partitioned into an independent set and a clique. A graph is a *co-bipartite graph* if its vertex set can be partitioned into two cliques.

A dominating set $D$ of $G$ is a *locating-dominating set*, abbreviated as LD-set, of $G$ if all vertices not in $D$ have pairwise distinct open neighborhoods in $D$. In other words, for every pair of vertices $u, v \in V(G) \setminus D$, we have $N_G(u) \cap D \neq N_G(v) \cap D$. The *location-domination number* of $G$, denoted by $\gamma_{LD}(G)$, is the minimum cardinality among all LD-sets of $G$. Slater [20] in 1988 introduced this variant of domination, namely location-domination. Since its birth, location-domination remained an active area of research (see [5, 13–16]). This is due to its relevance in network science and theoretical computer science. For a comprehensive overview of locating-dominating sets in graphs, we recommend the book chapter [18].

**1.1. Motivation**

Research on locating-dominating sets has been significantly influenced by a conjecture made by Garijo et al. [16] in 2014. Foucaud and Henning [14] later proposed a reformulation of this conjecture. The conjecture is stated below.

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

Garijo et al. [16] showed that if $G$ is a twin-free graph of order $n$, then $\gamma_{LD}(G) \le \lfloor \frac{2n}{3} \rfloor + 1$. Later, Foucaud et al. [15] subsequently improved this upper bound to $\lfloor \frac{2n}{3} \rfloor$. Recently, Bousquet et al. [5] further reduced the upper bound to $\lfloor \frac{5n}{8} \rfloor$, which is currently the best known bound to Conjecture 1. Conjecture 1 has not yet been proven, but has been shown to be true for some important graph classes.

**Theorem 1.1.** Conjecture 1 is true for isolate-free and twin-free graph $G$ of orders $n$ if at least one of the following is satisfied.

(a) [16] $G$ has no 4-cycle.

(b) [16] $G$ has independence number at least $\frac{n}{2}$.

(c) [16] $G$ has clique number at least $\lceil \frac{n}{2} \rceil + 1$.

(d) [3] $G$ has girth at least 5 and minimum degree at least 2.

(e) [15] $G$ is a split graph or a co-bipartite graph.

(f) [13] $G$ is a line graph.

(g) [11] $G$ is a maximal outerplanar graph.

(h) [6] $G$ is a block graph.

(i) [7] $G$ is a subcubic graph.

Given a graph $G$, if there exist two LD-sets $D_1$ and $D_2$ such that $D_1 \cup D_2 = V(G)$, $D_1 \cap D_2 = \emptyset$, then $[D_1, D_2]$ is called an *LD-partition* of $G$. Motivated by Conjecture 1, several authors have explored the following, a slightly stronger question.

**Question 1** ([8, 14–16]). For an isolate-free and twin-free graph $G$, does $G$ admit an LD-partition?
Recently, Chakraborty et al. [8] showed that if $G$ is an isolate-free (and not necessarily twin-free) graph, then $V(G)$ can be partitioned into a dominating set and an LD-set. It is already known that Question 1 has a positive answer for bipartite graphs [16] and block graphs [6], which naturally motivates investigating its validity in superclasses of these graph classes. In this context, we provide a positive answer to Question 1 for the class of distance-hereditary graphs, a well-known superclass of block graphs. Additionally, while Conjecture 1 is known to hold for maximal outerplanar graphs, split graphs, and co-bipartite graphs, we go further by establishing an affirmative answer to Question 1 for each of these graph classes as well.

This paper is organized as follows. In Section 2, we show that if $G$ is an isolate-free and twin-free distance-hereditary graph, then $G$ admits an LD-partition. In Section 3, we prove that every maximal outerplanar graph of order at least 4 admits an LD-partition. In Section 4, we prove that every isolate-free and twin-free split graph and co-bipartite graph also admits an LD-partition. Finally, in Section 5, we discuss potential directions for future research.

## 2. Distance-hereditary graphs

Our objective in this section is to show that every twin-free and isolate-free distance-hereditary graph admits an LD-partition. In this section, we assume that $G$ is a connected distance-hereditary graph.

Chang et al. [9] characterized distance-hereditary graphs via edge connections between two special sets of vertices, called twin sets. The comprehensive procedure is given in the next paragraph. At its base level, a graph $G$ with a single vertex $v$ is recognized as a distance-hereditary graph, endowed with the twin set $TS(G) = \{v\}$.

A distance-hereditary graph $G$ can be constructed from two existing vertex-disjoint distance-hereditary graphs, $G_l$ and $G_r$, each possessing twin sets $TS(G_l)$ and $TS(G_r)$, respectively, by using any of the subsequent three operations.

* If the true twin operation $\otimes$ is applied to construct the graph $G$ from $G_l$ and $G_r$, then

- The vertex set of $G$ is $V(G) = V(G_l) \cup V(G_r)$.

- The edge set of $G$ is $E(G) = E(G_l) \cup E(G_r) \cup \{v_1v_2|v_1 \in TS(G_l), v_2 \in TS(G_r)\}$.

- The twin set of $G$ is $TS(G) = TS(G_l) \cup TS(G_r)$.

* If the false twin operation $\odot$ is employed to construct the graph $G$ from $G_l$ and $G_r$, then

- The vertex set of $G$ is $V(G) = V(G_l) \cup V(G_r)$.

- The edge set of $G$ is $E(G) = E(G_l) \cup E(G_r)$.

- The twin set of $G$ is $TS(G) = TS(G_l) \cup TS(G_r)$.

* If the attachment operation $\oplus$ is employed to construct the graph $G$ from $G_l$ and $G_r$, then

- The vertex set of $G$ is $V(G) = V(G_l) \cup V(G_r)$.

- The edge set of $G$ is $E(G) = E(G_l) \cup E(G_r) \cup \{v_1v_2 | v_1 \in TS(G_l), v_2 \in TS(G_r)\}$.

- The twin set of $G$ is $TS(G) = TS(G_l)$.

By employing the three operations detailed above, one can systematically construct any distance-hereditary graph. This process leads to the creation of a binary tree representation for a given distance-hereditary graph $G$, commonly referred to as a *decomposition tree*. The definition of this tree is structured as follows: it articulates the sequence of operations through a full binary tree $T$, where the leaves of $T$ correspond to the vertices of $G$. Furthermore, each internal vertex in $T$ is assigned one of the labels $\otimes, \odot$, or $\oplus$, signifying the true twin operation, false twin operation, and attachment operation, respectively.
<figure><img src="image_2.png" /><figcaption>(a) A distance-hereditary graph G</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>(b) The decomposition tree $T_G$ of G</figcaption></figure>

<caption>Figure 1: An example of a distance-hereditary graph with its decomposition tree</caption>

In this representation, each leaf of $T$ corresponds to a distance-hereditary graph with a single vertex. A rooted subtree $T'$ of $T$ corresponds to the induced subgraph of $G$ on the vertices represented by the leaves of $T'$. Note that this induced subgraph is itself a distance-hereditary graph. For an internal vertex $v$ of $T$, the label of $v$ corresponds to the operation between the subgraphs represented by the subtrees rooted at the left and right children of $v$. Note that the order of the children only matters for the $\oplus$ operation. An example is illustrated in Figure 1.

Next, we prove the main theorem of this section.

**Theorem 2.1.** If $G$ is an isolate-free and twin-free distance-hereditary graph, then $G$ admits an LD-partition.

*Proof.* We prove this using induction on $|V(G)| + |E(G)| = n + m$. For the base cases, it can be easily checked for all isolate-free and twin-free distance-hereditary graphs of order 4 (as the only example of twin-free and isolate-free distance-hereditary graph of order 4 is $P_4$). So, let the statement be true for all isolate-free and twin-free distance-hereditary graphs of order $< n + m$.

Let $G$ be an isolate-free and twin-free distance-hereditary graph of order $n$. Suppose $G$ is disconnected. Let $G_1, G_2, \dots, G_k$ be the components of $G$. Then by the induction hypothesis, each $G_i$ admits an LD-partition $[D_1^i, D_2^i]$ for all $i \in \{1, 2, \dots, k\}$. Let $D_1 = D_1^1 \cup D_1^2 \cup \dots \cup D_1^k$ and $D_2 = D_2^1 \cup D_2^2 \cup \dots \cup D_2^k$. Then $[D_1, D_2]$ is an LD-partition of $G$. So we assume that $G$ is connected. Let $T_G$ be the decomposition tree of $G$. Consider the BFS levels of $T_G$ and let $t$ be an internal node of $T_G$ that is situated at the second last BFS level. Note that both children (say $a$ and $b$) of $t$ are vertices of $G$.

Suppose $t$ has label $\odot$ (or $\otimes$). This implies that $a$ and $b$ are false twin (or true twin), which contradicts the fact that $G$ is twin-free. Hence, $t$ has label $\oplus$. Let $t'$ be the parent of $t$. Now, a vertex $t'$ can be labeled as $\odot$, $\otimes$, or $\oplus$. Moreover, if $t'$ has the label $\oplus$ and its child is a leaf node, then two cases arise: either $t$ is the left child of $t'$, or $t$ is the right child of $t'$. Moreover, if the child of $t'$ other than $t$, say $t''$, is an internal node, then $t''$ has the label $\oplus$ (a similar argument can be given as the one used to show that $t'$ has the label $\oplus$). Based on these observations, we consider the following cases.

(1) $t'$ has label $\oplus$, $t$ is the right child of $t'$, and the left child of $t'$ is a leaf node $c$;

(2) $t'$ has label $\oplus$, $t$ is the left child of $t'$, and the right child of $t'$ is a leaf node $c$;

(3) $t'$ has label $\odot$ and the other child of $t'$ is a leaf node $c$;

(4) $t'$ has label $\otimes$ and the other child of $t'$ is a leaf node $c$;

(5) $t'$ has label $\oplus$ and the other child of $t'$ is an internal node $t''$ which also has label $\oplus$;

(6) $t'$ has label $\odot$ and the other child of $t'$ is an internal node $t''$ which has label $\oplus$;

(7) $t'$ has label $\otimes$ and the other child of $t'$ is an internal node $t''$ which has label $\oplus$.

We now analyze these cases separately.
**Case 1:** $t'$ has label $\oplus$, $t$ is the right child of $t'$, and the left child of $t'$ is a node $c$. For a clear understanding, see Figure 2.

<figure><img src="image_4.png" /><figcaption>Figure 2: The subtree of $T_G$ rooted at $t'$ in Case 1</figcaption></figure>

Let $G_1 = G \setminus \{a, b\}$. If $G_1$ is twin-free and isolate-free, then by the induction hypothesis, $G_1$ admits an LD-partition $[D_1, D_2]$. Without loss of generality, let $c \in D_1$ and $c \notin D_2$. Define $D'_1 = D_1 \cup \{b\}$ and $D'_2 = D_2 \cup \{a\}$. Observe that $[D'_1, D'_2]$ is an LD-partition of $G$. If $G_1$ is not twin-free, then there exists a vertex in $V(G_1)$, say $x$, such that $c$ and $x$ are twins in $G_1$. In the following, we consider two cases and in each case, we prove that $G$ admits an LD-partition.

**Case 1.1:** $c$ and $x$ are false twins in $G_1$.

<figure><img src="image_5.png" /><figcaption>Figure 3: Case 1</figcaption></figure>

Let $G' = G \setminus \{a, b, c\}$. Suppose there exist twins in $G'$, say $y$ and $z$. Clearly, exactly one of $y$ and $z$ is adjacent to $c$, which implies that exactly one of $y$ and $z$ is adjacent to $x$. Since $x \in V(G')$, $N_{G'}(y) \neq N_{G'}(z)$, contradicting that $y$ and $z$ are twins. Hence, $G'$ is twin-free. Then by the induction hypothesis, let $[D_1, D_2]$ be an LD-partition of $G'$ such that $x \in D_1$ and $x \notin D_2$. We define $D'_1 = D_1 \cup \{c, b\}$ and $D'_2 = D_2 \cup \{a\}$. It is easy to check that $D'_1$ is an LD-set of $G$.

Clearly, $D'_2$ is a dominating set of $G$. For the sake of contradiction, assume that $D'_2$ is not an LD-set of $G$. This implies that there exist two vertices in $V(G) \setminus D'_2$ which have the same neighborhood in $D'_2$. The only candidates for these two vertices are $c$ and $b$ (as the rest of the vertices in $V(G) \setminus D'_2$ have different neighborhoods in $D'_2$ since $D_2$ is an LD-set of $G'$). But note that $x$ is dominated by some vertex $z$ in $D_2$, so $N_G(z)$ contains $c$ but not $b$, which contradicts the fact that $c$ and $b$ have the same neighborhood in $D'_2$. This implies that $D'_2$ is an LD-set. So $[D'_1, D'_2]$ is an LD-partition of $G$.

**Case 1.2:** $c$ and $x$ are true twins of $G_1$.

Let $G' = G \setminus \{b\}$. Note that $G'$ is a twin-free distance-hereditary graph. By the induction hypothesis, let $[D_1, D_2]$ be an LD-partition of $G'$. If $\{c, a\} \subseteq D_1$, then $c$ and $a$ do not belong to $D_2$, which contradicts the fact that $D_2$ is a dominating set. So $\{c, a\} \not\subseteq D_1$. Similarly, $\{c, a\} \not\subseteq D_2$. Hence, without loss of
generality, let $c \in D_1$ and $a \in D_2$. We define $D'_1 = D_1 \cup \{b\}$ and $D'_2 = D_2$. Clearly, $D'_1$ is an LD-set of $G$ and $D'_2$ is a dominating set of $G$. For the sake of contradiction, assume that $D'_2$ is not an LD-set of $G$, this implies that $N_G(c) \cap D'_2 = N_G(b) \cap D'_2 = \{a\}$. This means $N_{G'}[c] \cap D'_2 = N_{G'}[c] \cap D_2 = \{a\}$, implying $N_{G'}[x] \cap D_2 = \emptyset$ which contradicts the fact that $D_2$ is a dominating set of $G'$. Hence, $[D'_1, D'_2]$ is an LD-partition of $G$.

**Case 2:** $t'$ has label $\oplus$, $t$ is the left child of $t'$, and the right child of $t'$ is a node $c$. For clear understanding, see Figure 4.

<figure><img src="image_6.png" /><figcaption>Figure 4: The subtree of $T_G$ rooted at $t'$ in Case 2</figcaption></figure>

In this case, $b$ and $c$ are leaves in $G$ that are adjacent to the vertex $a$. Hence $b$ and $c$ are twins, which contradicts the fact that $G$ is twin-free. So this is not a valid case.

**Case 3:** $t'$ has label $\odot$ and the other child of $t'$ is a leaf node $c$. For clear understanding, see Figure 5.

<figure><img src="image_7.png" /><figcaption>Figure 5: The subtree of $T_G$ rooted at $t'$ in Case 3</figcaption></figure>

Let $G' = G \setminus \{a, b\}$. By similar arguments as in Case 1, it can be shown that $G'$ is also twin-free and isolate-free. By the induction hypothesis, let $[D_1, D_2]$ be an LD-partition of $G'$. Without loss of generality, let $c \in D_1$ and $c \notin D_2$. We define $D'_1 = D_1 \cup \{a\}$ and $D'_2 = D_2 \cup \{b\}$. By using analogous arguments like in Case 1.1, it can be shown that $[D'_1, D'_2]$ is an LD-partition of $G$.

**Case 4:** $t'$ has label $\otimes$ and the other child of $t'$ is a leaf node $c$. For clear understanding, see Figure 6.

Let $G'$ be obtained from $G$ by deleting all the edges between $N_G(c) \setminus \{a\}$ and $a$. By using similar arguments as in Case 1, it can be proved that $G'$ is twin-free. Let $G'' = G' \setminus \{a, b\}$. Note that $G'$ and $G''$ are isolate-free. In the following, we consider two cases and in each case, we prove that $G$ admits an LD-partition.

**Case 4.1:** $G''$ is twin-free.

By the induction hypothesis, $G''$ admits an LD-partition $[D_1, D_2]$ such that $c \in D_1$. We define $D'_1 = D_1 \cup \{a\}$ and $D'_2 = D_2 \cup \{b\}$. By using analogous arguments as in Case 1.1, it can be shown that $[D'_1, D'_2]$ is an LD-partition of $G$.
<figure><img src="image_8.png" /><figcaption>Figure 6: The subtree of $T_G$ rooted at $t'$ in Case 4</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 7: Case 4.2 ($c$ and $x$ are false twins in $G''$)</figcaption></figure>

**Case 4.2:** $G''$ is not twin-free.

Since $G''$ is not twin-free, there exists a vertex in $V(G'')$, say $x$, such that $c$ and $x$ are twins in $G''$. First we prove that $c$ and $x$ are false twins. For the sake of contradiction, let $c$ and $x$ be true twins in $G''$, implying $x \in N_G(c) \subseteq N_G(a)$. Hence $N_{G''}(x) = N_{G''}(c)$ implies that $N_G[x] = N_G[c]$, which contradicts the fact that $G$ is twin-free. Hence, $c$ and $x$ must be false twins in $G''$ (refer to Figure 7).

Recall that $G'$ is twin-free. Note that $G'$ has same structure as in Case 1.1. Hence, by the analysis of Case 1.1 and induction hypothesis, it can be concluded that, $G'$ admits an LD-partition $[D_1, D_2]$ such that $D_1$ contains $x, c, b$ and $D_2$ contains $a$. It is easy to see that $D_1$ is also an LD-set of $G$.

Next, we prove that $D_2$ is an LD-set of $G$. Note that $D_2$ is a dominating set of $G$, as it is a dominating set of $G'$. For the sake of contradiction, assume that $D_2$ is not an LD-set of $G$. This implies that adding back the deleted edges has created some problem. Hence, there exists $y \in V(G)$ such that $N_G(y) \cap D_2 = N_G(c) \cap D_2$. This implies that $N_{G'}(y) \cap D_2 = (N_{G'}(c) \cap D_2) \setminus \{a\}$, implying $N_{G'}(y) \cap D_2 = N_{G'}(x) \cap D_2$ which contradicts the fact that $D_2$ is an LD-set in $G'$. Hence $D_2$ is an LD-set in $G$. So $[D_1, D_2]$ is an LD-partition of $G$.

**Case 5:** $t'$ has label $\oplus$ and the other child of $t'$ is an internal node $t''$ which also has label $\oplus$. For a clear understanding, see Figure 8.

<figure><img src="image_10.png" /><figcaption>Figure 8: Case 5</figcaption></figure>

Let $G' = G \setminus \{c, d\}$. Observe that $G'$ is a twin-free and isolate-free distance-hereditary graph. By the
induction hypothesis, $G'$ admits an LD-partition $[D_1, D_2]$ such that $D_1$ contains $a$ and $D_2$ contains $b$. We define $D'_1 = D_1 \cup \{c\}$ and $D'_2 = D_2 \cup \{d\}$. It is easy to observe that $[D'_1, D'_2]$ is an LD-partition of $G$.

**Case 6:** $t'$ has label $\odot$ and the other child of $t'$ is an internal node $t''$ which has label $\oplus$. Refer to Figure 9 for clear understanding.

<figure><img src="image_11.png" /><figcaption>Figure 9: Case 6</figcaption></figure>

Let $G' = G \setminus \{c, d\}$. Observe that $G'$ is a twin-free and isolate-free distance-hereditary graph. By the induction hypothesis, $G'$ admits an LD-partition $[D_1, D_2]$ such that $D_1$ contains $a$ and $D_2$ contains $b$. We define $D'_1 = D_1 \cup \{c\}$ and $D'_2 = D_2 \cup \{d\}$. It is easy to observe that $[D'_1, D'_2]$ is an LD-partition of $G$.

**Case 7:** $t'$ has label $\otimes$ and the other child of $t'$ is an internal node $t''$ which has label $\oplus$. Refer to Figure 10 for clear understanding.

<figure><img src="image_12.png" /><figcaption>Figure 10: Case 7</figcaption></figure>

Let $G' = G \setminus \{c, d\}$. Observe that $G'$ is a twin-free and isolate-free distance-hereditary graph. By the induction hypothesis, $G'$ admits an LD-partition $[D_1, D_2]$ such that $D_1$ contains $a$ and $D_2$ contains $b$. We define $D'_1 = D_1 \cup \{c\}$ and $D'_2 = D_2 \cup \{d\}$. It is easy to observe that $[D'_1, D'_2]$ is an LD-partition of $G$.
This completes the proof of Theorem 2.1. □

### 3. Maximal Outerplanar graphs

Note that the only mops with twin vertices are those of order 3 and 4: the cycle of order 3, and the graph obtained by deleting an edge from the complete graph of order 4. In question 1, we are only interested in the twin-free graphs. However, in this section, we prove that every mop of order at least 4 has an LD-partition. To prove the above result, we need the following observation.

**Observation 3.1.** If $G$ is a mop of order 4 or 5, then there exists a vertex adjacent to all other vertices of $G$.
Let $G$ be a mop of order $n \ge 4$ vertices. Hence, there exists a plane embedding of $G$ such that all vertices of $G$ are on the outer face, and all inner faces are triangles. We construct a new graph $T$ associated with a given mop $G$ as follows.

* Each vertex of $T$ represents a triangle in $G$.

* Two vertices in $T$ are adjacent by an edge if their corresponding triangles in $G$ share an edge.

Note that $T$ is connected. If $T$ has a cycle, then there exists a vertex in $G$ that is enclosed by triangles, which is not possible since $G$ is outerplanar. So $T$ must be a tree. The maximum degree of any vertex in $T$ is at most 3. We will analyze the tree $T$ and understand its corresponding structure in mop $G$.

**Theorem 3.1.** If $G$ is a mop of order at least 4, then $G$ admits an LD-partition.

*Proof.* Let $G$ be a mop of order $n \ge 4$. We will use induction on $n$. Let $v_1v_2v_3\dots v_nv_1$ be the vertices on the outer face of $G$, listed in order. If $n=4$, then by Observation 3.1, without loss of generality, assume that $v_1$ is adjacent to $v_2, v_3$, and $v_4$ in $G$. Since $G$ is a mop, $v_2v_4 \notin E(G)$. Then $\{v_1, v_2\}$ and $\{v_3, v_4\}$ are LD-sets of $G$. If $n=5$, then by Observation 3.1, without loss of generality, assume that $v_1$ is adjacent to $v_2, v_3, v_4$, and $v_5$ in $G$. Since $G$ is a mop, $v_2v_4, v_2v_5, v_3v_5 \notin E(G)$. Then $\{v_1, v_2, v_5\}$ and $\{v_3, v_4\}$ are LD-sets of $G$. So assume that $n \ge 6$.

Let $T$ be the tree associated with the mop $G$, where $T$ is rooted at a leaf $w$. Since $T$ has at least two leaves, there exists a leaf other than $w$, say $y$. Since $n \ge 6$, $|V(T)| \ge 4$. Let $x$ be the parent of $y$ in $T$. We define $T_x$ as the subtree of $T$ that is rooted at the vertex $x$. Since the maximum degree of $T$ is at most 3, $x$ has at most two children in $T$. In the following, we consider two cases based on the number of children of $x$.

**Case 1:** $x$ has two children in $T$.

Let $z$ be a child of $x$ other than $y$. Let $R_x$ be the triangle in $G$ corresponding to the vertex $x$. Let $V(R_x) = \{v_1, v_2, v_3\}$. Let $R_y$ and $R_z$ be the triangles in $G$ corresponding to the vertices $y$ and $z$, respectively. Further, let $V(R_y) = \{v_1, v_3, v_4\}$ and $V(R_z) = \{v_2, v_3, v_5\}$. Thus, $G$ contains the subgraph illustrated in Figure 11(b), where the shaded triangle corresponds to the vertex $x$ in $T_x$. Since $y$ and $z$ are leaves in $T$, we have that $\deg_G(v_4) = \deg_G(v_5) = 2$ and $\deg_G(v_3) = 4$. Recall that $n \ge 6$.

<figure><img src="image_13.png" /><figcaption>Figure 11: Subtree $T_x$ and possible subgraph of $G$.</figcaption></figure>

Let $H$ be the graph of order $n'$ obtained from $G$ by deleting the vertices $v_4$ and $v_5$. Since $n \ge 6$, we have $n' = n - 2 \ge 4$. We note that $H$ is also a mop. Then by the induction hypothesis, let $[D'_1, D'_2]$ be an LD-partition of $H$. Since $\deg_H(v_3) = 2$, each $D'_i$ contains at least one vertex from the set $\{v_1, v_2, v_3\}$ for $i \in \{1, 2\}$. In the following, we consider three cases and in each case, we prove that $G$ admits an LD-partition.

**Case 1.1:** $v_1, v_2 \in D'_1$ and $v_3 \in D'_2$.
Let $D_1 = D'_1 \cup \{v_3\}$ and $D_2 = (D'_2 \setminus \{v_3\}) \cup \{v_4, v_5\}$. Now we show that each $D_i$ is an LD-set of $G$ for $i \in \{1,2\}$. Since $N_G(v_4) \cap D_1 = \{v_1, v_3\}$ and $N_G(v_5) \cap D_1 = \{v_2, v_3\}$, $D_1$ is an LD-set of $G$. Note that $N_G(v_1) \cap \{v_4, v_5\} = \{v_4\}$, $N_G(v_2) \cap \{v_4, v_5\} = \{v_5\}$, and $N_G(v_3) \cap \{v_4, v_5\} = \{v_4, v_5\}$. Moreover, $\{v_4, v_5\} \subset D_2$. Therefore, $D_2$ is an LD-set of $G$.

**Case 1.2:** $v_1, v_3 \in D'_1$ and $v_2 \in D'_2$.

Let $D_1 = D'_1 \cup \{v_5\}$ and $D_2 = D'_2 \cup \{v_4\}$. Now we show that each $D_i$ is an LD-set of $G$ for $i \in \{1,2\}$. Note that $N_G(v_2) \cap \{v_1, v_3, v_5\} = \{v_1, v_3, v_5\}$ and $N_G(v_4) \cap \{v_1, v_3, v_5\} = \{v_1, v_3\}$. Moreover, $\{v_1, v_3, v_5\} \subset D_1$. Therefore, $D_1$ is an LD-set of $G$. Since $D'_2$ is an LD-set of $H$, we have $N_H(v_1) \cap D'_2 \neq N_H(v_3) \cap D'_2$. Hence $N_G(v_1) \cap D_2 \neq N_G(v_3) \cap D_2$. Note that $\{v_2, v_4\} \subseteq N_G(v_1) \cap D_2$, $N_G(v_3) \cap D_2 = \{v_2, v_4\}$, and $N_G(v_5) \cap D_2 = \{v_2\}$. Therefore, $D_2$ is an LD-set of $G$.

**Case 1.3:** $v_2, v_3 \in D'_1$ and $v_1 \in D'_2$.

Let $D_1 = D'_1 \cup \{v_4\}$ and $D_2 = D'_2 \cup \{v_5\}$. We can make similar arguments as we did in Case 1.2. Hence $G$ admits an LD-partition $[D_1, D_2]$.

**Case 2:** $x$ has only one child in $T$.

Since $n \ge 6$, $|V(T)| \ge 4$. So the parent of $x$ exists in $T$. Let $x'$ be the parent of $x$ in $T$. Recall that $x$ is the parent of $y$ in $T$. Let $R_{x'}$ be the triangle in $G$ corresponding to the vertex $x'$. Let $V(R_{x'}) = \{v_1, v_2, v_3\}$. Let $R_x$ and $R_y$ be the triangles in $G$ corresponding to the vertices $x$ and $y$, respectively. Further, due to symmetry, without loss of generality, assume that $V(R_x) = \{v_1, v_2, v_4\}$ and $V(R_y) = \{v_2, v_4, v_5\}$. Thus, $G$ contains the subgraph illustrated in Figure 12(b), where the shaded triangle corresponds to the vertex $x'$ in $T_{x'}$. Since $y$ is a leaf and $x$ has exactly one child in $T$, we have $\deg_G(v_5) = 2$ and $\deg_G(v_4) = 3$.

<figure><img src="image_14.png" /><figcaption>Figure 12: Subtree $T_{x'}$ and possible subgraph of $G$.</figcaption></figure>

Let $H$ be the graph of order $n'$ obtained from $G$ by deleting the vertices $v_4$ and $v_5$. Since $n' \ge 6$, we have $n' = n - 2 \ge 4$. We note that $H$ is also a mop. Then by the induction hypothesis, let $[D'_1, D'_2]$ be an LD-partition of $H$. In the following, we consider four cases and in each case, we prove that $G$ admits an LD-partition.

**Case 2.1:** $v_1, v_2 \in D'_1$ and $v_3 \in D'_2$.

Let $D_1 = D'_1 \cup \{v_5\}$ and $D_2 = D'_2 \cup \{v_4\}$. Now we show that each $D_i$ is an LD-set of $G$ for $i \in \{1,2\}$. Note that $N_G(v_3) \cap \{v_1, v_2, v_5\} = \{v_1, v_2\}$ and $N_G(v_4) \cap \{v_1, v_2, v_5\} = \{v_1, v_2, v_5\}$. Moreover, $\{v_1, v_2, v_5\} \subset D_1$. Therefore, $D_1$ is an LD-set of $G$. Since $D'_2$ is an LD-set of $H$, we have $N_H(v_1) \cap D'_2 \neq N_H(v_2) \cap D'_2$. Hence $N_G(v_1) \cap D_2 \neq N_G(v_2) \cap D_2$. Note that $\{v_3, v_4\} \subseteq N_G(v_1) \cap D_2$, $\{v_3, v_4\} \subseteq N_G(v_2) \cap D_2$, and $N_G(v_5) \cap D_2 = \{v_4\}$. Therefore, $D_2$ is an LD-set of $G$.

**Case 2.2:** $v_1, v_3 \in D'_1$ and $v_2 \in D'_2$.

Let $D_1 = D'_1 \cup \{v_4\}$ and $D_2 = D'_2 \cup \{v_5\}$. Now we show that each $D_i$ is an LD-set of $G$ for $i \in \{1,2\}$. Note that $N_G(v_2) \cap \{v_1, v_3, v_4\} = \{v_1, v_3, v_4\}$ and $N_G(v_5) \cap \{v_1, v_3, v_4\} = \{v_4\}$. Moreover, $\{v_1, v_3, v_4\} \subset D_1$. Therefore, $D_1$ is an LD-set of $G$. Since $D'_2$ is an LD-set of $H$, we have $N_H(v_1) \cap D'_2 \neq N_H(v_3) \cap D'_2$. Hence
$N_G(v_1) \cap D_2 \neq N_G(v_3) \cap D_2$. Note that $v_5 \notin N_G(v_1) \cap D_2$, $v_5 \notin N_G(v_2) \cap D_2$, and $N_G(v_4) \cap D_2 = \{v_2, v_5\}$. Therefore, $D_2$ is an LD-set of $G$.

**Case 2.3:** $v_2, v_3 \in D'_1$ and $v_1 \in D'_2$.

Let $D_1 = D'_1 \cup \{v_5\}$ and $D_2 = D'_2 \cup \{v_4\}$. We can make similar arguments as we did in Case 2.2.

**Case 2.4:** $v_1, v_2, v_3 \in D'_1$ and $v_1, v_2, v_3 \notin D'_2$.

Let $D_1 = D'_1 \cup \{v_4\}$ and $D_2 = D'_2 \cup \{v_5\}$. Clearly, $D_1$ is an LD-set of $G$. Now we show that $D_2$ is an LD-set of $G$. Since $D'_2$ is an LD-set of $H$, $N_H(v_1) \cap D'_2$, $N_H(v_2) \cap D'_2$, and $N_H(v_3) \cap D'_2$ are distinct and nonempty sets. Hence $N_G(v_1) \cap D_2$, $N_G(v_2) \cap D_2$, and $N_G(v_3) \cap D_2$ are distinct and nonempty sets. Note that $N_G(v_4) \cap D_2 = \{v_5\}$. Moreover, we have $N_G(v_i) \cap D_2 \neq N_G(v_4) \cap D_2$ for all $i \in \{1, 2, 3\}$ since $D'_2$ is an LD-set of $H$. Therefore, $D_2$ is an LD-set of $G$. $\square$

# 4. Split graphs and co-bipartite graphs

In this section, we show that every isolate-free and twin-free split graph and co-bipartite graph admit LD-partitions. In [15], it has been proved that if $G$ is a twin-free and isolate-free split graph or co-bipartite graph, then $\gamma_{LD}(G) \leq \frac{n}{2}$. Our proofs are an extension of the ones from [15] used to prove Conjecture 1 for split and co-bipartite graphs, but the key arguments are similar.

**Theorem 4.1.** If $G$ is an isolate-free and twin-free split graph, then $G$ admits an LD-partition.

*Proof.* Assume that $G$ is an isolate-free and twin-free split graph. Let $X$ be a clique of $G$ and $Y$ be an independent set of $G$ such that $X \cap Y = \emptyset$ and $X \cup Y = V(G)$. Note that every vertex in $Y$ has at least one neighbor in $X$. Moreover, for every $a, b \in X$, we have $N_G(a) \cap Y \neq N_G(b) \cap Y$ since $G$ is twin-free. Further, for every $c, d \in Y$, we have $N_G(c) \cap X \neq N_G(d) \cap X$.

We may assume that the set $S = \{a \in X \mid N_G(a) \cap Y = \emptyset\}$ is empty (otherwise, $S$ has exactly one vertex, say $S = \{u\}$, and letting $X' = X \setminus \{u\}$ and $Y' = Y \cup \{u\}$, we obtain that the set $S' = \{a \in X' \mid N_G(a) \cap Y' = \emptyset\}$ is empty). Under this assumption, $[X, Y]$ is already an LD-partition of $G$. Thus $G$ admits an LD-partition. $\square$

**Theorem 4.2.** If $G$ is an isolate-free and twin-free co-bipartite graph, then $G$ admits an LD-partition.

*Proof.* Assume that $G$ is an isolate-free and twin-free co-bipartite graph. Let $X$ and $Y$ be the two cliques of $G$ such that $X \cap Y = \emptyset$ and $X \cup Y = V(G)$. Let $S_1 = \{a \in X \mid N_G(a) \cap Y = \emptyset\}$ and $S_2 = \{c \in Y \mid N_G(c) \cap X = \emptyset\}$. Since $G$ is twin-free, we have $N_G(a) \cap Y \neq N_G(b) \cap Y$ and $N_G(c) \cap X \neq N_G(d) \cap X$ for every $a, b \in X$ and $c, d \in Y$. So $|S_1| \leq 1$ and $|S_2| \leq 1$.

If $S_1 = \emptyset$ and $S_2 = \emptyset$, then $X$ and $Y$ are LD-sets of $G$ and so $G$ admits an LD-partition. Suppose now that at least one of the sets from $S_1$ and $S_2$ is nonempty. First suppose that $|S_1| = 1$ and $|S_2| = 1$. Let $X' = (X \setminus S_1) \cup S_2$ and $Y' = (Y \setminus S_2) \cup S_1$. Now we show that $X'$ and $Y'$ are LD-sets of $G$. It is easy to observe that $X'$ is a dominating set of $G$. Since $N_G(c) \cap X \neq N_G(d) \cap X$ for every $c, d \in Y$, $N_G(c) \cap X' \neq N_G(d) \cap X'$ for every $c, d \in Y \setminus \{S_2\}$. Since $|S_2| = 1$, we have $N_G(x) \cap X' \neq N_G(y) \cap X'$ for $x \in S_1$ and every $y \in Y \setminus \{S_2\}$. Hence $X'$ is an LD-set of $G$. Similarly, $Y'$ is also an LD-set of $G$ and so $G$ admits an LD-partition. Hence there exists a vertex $y \in Y$ such that $N_G(y) \cap X \setminus \{x\} = X \setminus \{x\}$. Note that there is no vertex $y' \in Y$ other than $y$ such that $N_G(y') \cap X \setminus \{x\} = X \setminus \{x\}$; otherwise, $G$ contains twins. Let $X' = (X \setminus \{x\}) \cup \{y\}$ and $Y' = (Y \setminus \{y\}) \cup \{x\}$. Clearly, $X'$ is an LD-set of $G$. Now we show that $Y'$ is an LD-set of $G$. Note that $N_G(y) \cap Y' = Y' \setminus \{x\}$ and $N_G(v) \cap Y' \neq \emptyset$ for all $v \in X \setminus \{x\}$. Moreover, every vertex in $X \setminus \{x\}$ has distinct neighborhood in $Y'$ since $G$ is twin-free and $x \in Y'$. Hence $Y'$ is also an LD-set of $G$. Thus $G$ admits an LD-partition. $\square$
## 5. Conclusion

Conjecture 1 is already known to hold for several important graph classes, including bipartite graphs, split graphs, co-bipartite graphs, line graphs, maximal outerplanar graphs, subcubic graphs, and block graphs. In this work, we addressed Question 1 and provided a positive answer for well-structured graph classes, namely distance-hereditary graphs, maximal outerplanar graphs, split graphs, and co-bipartite graphs.

This work contributes to a deeper structural understanding of locating-dominating sets and their properties within well-defined graph classes. As a natural direction for future research, it would be worthwhile to investigate whether Conjecture 1 holds for the class of chordal graphs.

## Acknowledgements

Research of Florent Foucaud and Kaustav Paul was partially funded by the ANR project GRALMECO (ANR-21-CE48-0004), the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25), the International Research Center “Innovation Transportation and Production Systems” of the I-SITE CAP 20-25, and the CNRS IRL ReLaX.

## Declarations

**Conflict of interest** The authors do not have any financial or non financial interests that are directly or indirectly related to the work submitted for publication.

**Data availability** No data was used for the research described in this paper.

## References

[1] J. D. Alvarado, S. Dantas, D. Rautenbach, Dominating sets inducing large components in maximal outerplanar graphs, J. Graph Theory 88 (2018) 356–370.

[2] T. Araki, I. Yumoto, On the secure domination numbers of maximal outerplanar graphs, Discrete Appl. Math. 236 (2018) 23–29.

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

[4] S. Banerjee, J. Chaudhary, D. Pradhan, Unique response Roman domination: complexity and algorithms, Algorithmica 85 (12) (2023) 3889–3927.

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

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

[7] D. Chakraborty, A. Hakanen, T. Lehtilä, The $n/2$-bound for locating-dominating sets in subcubic graphs, https://arxiv.org/abs/2406.19278 (2024).

[8] D. Chakraborty, F. Foucaud, M. A. Henning, T. Laihonen, A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set, https://hal.science/hal-05022831 (2025).

[9] M. S. Chang, S. Y. Hsieh, G. H. Chen, Dynamic programming on distance-hereditary graphs, Proceedings of Seventh International Symposium on Algorithms and Computation (ISAAC’97), Lecture Notes in Computer Science 1350 (1997) 344–353.
[10] V. Chvátal, A combinatorial theorem in plane geometry, J. Combin. Theory Ser. B 18 (1975) 39–41.

[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) 2603–2630.

[12] M. Dorfling, J. H. Hattingh, E. Jonck, Total domination in maximal outerplanar graphs II, Discrete Math. 339 (3) (2016) 1180–1188.

[13] F. Foucaud, M. A. Henning, Location-domination in line graphs, Discrete Math. 340 (2017) 3140–3153.

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

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

[16] D. Garijo, A. González, A. Márquez, The difference between the metric dimension and the determining number of a graph, Appl. Math. Comput. 249 (2014) 487–501.

[17] M. Liedloff, T. Kloks, J. Liu, S. L. Peng, Efficient algorithms for Roman domination on some classes of graphs, Discrete Appl. Math. 156 (2008) 3400–3415.

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

[19] K. Paul, A. Sharma, A. Pandey, Exploring algorithmic solutions for the Independent Roman Domination problem in graphs. Discrete Appl. Math. 364 (2025) 143–152.

[20] P. J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (4) (1988) 445–455.