Locating-dominating partitions for some classes of graphs

A dominating set of a graph G is a set D ⊆ V(G) such that every vertex in V(G) D is adjacent to at least one vertex in D. A set L⊆ V(G) is a locating set of G if every vertex in V(G) L has pairwise distinct open neighborhoods in L. A set D⊆ 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 γ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 γLD(G)≤ 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 γLD(G)≤ 5n/8 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 that 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.