pith. sign in

arxiv: 2506.12933 · v2 · submitted 2025-06-15 · 🧮 math.CO · cs.DM

Locating-dominating partitions for some classes of graphs

Florent Foucaud , Paras Vinubhai Maniya , Kaustav Paul , Dinabandhu Pradhan This is my paper

Pith reviewed 2026-05-19 09:17 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords locating-dominating setsgraph partitionsdistance-hereditary graphsmaximal outerplanar graphssplit graphsco-bipartite graphslocation-domination number
0
0 comments X

The pith

Graphs without isolates or twins in four classes can have their vertices split into two locating-dominating sets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out to prove that distance-hereditary graphs, maximal outerplanar graphs, split graphs, and co-bipartite graphs, when free of isolated vertices and twin vertices, admit a partition of their vertex set into two locating-dominating sets. A sympathetic reader would care because such a partition immediately yields that the smallest locating-dominating set has size at most half the number of vertices, confirming a known conjecture for these structured classes. The result also strengthens an earlier question about partitions into locating sets alone by requiring the stronger dominating property as well.

Core claim

The authors prove that for any graph G without isolated vertices and without 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. This also confirms the conjecture that the location-domination number is at most n/2 for graphs in these classes.

What carries the argument

A locating-dominating set: a vertex subset that dominates every vertex outside it and assigns each outside vertex a unique pattern of neighbors inside the set.

If this is right

  • The location-domination number is at most half the order for every isolate-free twin-free graph in these four classes.
  • A partition into two locating sets exists for these graphs because a stronger partition into locating-dominating sets is guaranteed.
  • The result holds uniformly across distance-hereditary graphs, maximal outerplanar graphs, split graphs, and co-bipartite graphs under the stated conditions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same partition guarantee might extend to other hereditary classes that avoid isolates and twins.
  • Constructive proofs for these partitions could be turned into polynomial-time procedures for finding balanced locating-dominating sets in the listed graph families.

Load-bearing premise

The graph must belong to one of the four listed classes while also having no isolated vertices and no twin vertices.

What would settle it

A single graph belonging to one of the four classes, with no isolated vertices and no twin vertices, whose vertex set cannot be partitioned into two locating-dominating sets.

Figures

Figures reproduced from arXiv: 2506.12933 by Dinabandhu Pradhan, Florent Foucaud, Kaustav Paul, Paras Vinubhai Maniya.

Figure 1
Figure 1. Figure 1: An example of a distance-hereditary graph with its [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The subtree of TG rooted at t ′ in Case 1 Let G1 = G \ {a, b}. If G1 is twin-free and isolate-free, then by the induction hypothesis, G1 admits an LD-partition [D1, D2]. Without loss of generality, let c ∈ D1 and c /∈ D2. Define D′ 1 = D1 ∪ {b} and D′ 2 = D2 ∪ {a}. Observe that [D′ 1 , D′ 2 ] is an LD-partition of G. If G1 is not twin-free, then there exists a vertex in V (G1), say x, such that c and x are… view at source ↗
Figure 3
Figure 3. Figure 3: Case 1 Let G′ = G \ {a, b, c}. Next, we prove the following claim: Claim 2.1. G′ is twin-free. 5 [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The subtree of TG rooted at t ′ in Case 2 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 ⊙ and the other child of t ′ is a leaf node c. For clear understanding, see [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The subtree of TG rooted at t ′ in Case 3 G′′ are twin-free and isolate-free. In the following, we consider two cases and in each case, we prove that G admits an LD-partition. (a) Subtree of TG rooted at t ′ (b) G [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The subtree of TG rooted at t ′ in Case 4 Case 4.1: G′′ is twin-free. By the induction hypothesis, G′′ admits an LD-partition [D1, D2] such that c ∈ D1. We define D′ 1 = D1 ∪ {a} and D′ 2 = D2 ∪ {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. Case 4.2: G′′ is not twin-free [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Case 4.2 (c and x are false twins in G′′) 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 ∈ NG(c) ⊆ NG(a). Hence NG′′(x) = NG′′(c) implies that NG[x] = NG[c], which contradicts the fact that G is twin-free. Hence, c and x must be… view at source ↗
Figure 8
Figure 8. Figure 8: Case 5 Let G′ = G \ {c, d}. Observe that G′ is a twin-free and isolate-free distance-hereditary graph. By the induction hypothesis, G′ admits an LD-partition [D1, D2] such that D1 contains a and D2 contains b. We define D′ 1 = D1 ∪ {c} and D′ 2 = D2 ∪ {d}. It is easy to observe that [D′ 1 , D′ 2 ] is an LD-partition of G. Case 6: t ′ has label ⊙ and the other child of t ′ is an internal node t ′′ which has… view at source ↗
Figure 9
Figure 9. Figure 9: Case 6 Let G′ = G \ {c, d}. Observe that G′ is a twin-free and isolate-free distance-hereditary graph. By the induction hypothesis, G′ admits an LD-partition [D1, D2] such that D1 contains a and D2 contains b. We define D′ 1 = D1 ∪ {c} and D′ 2 = D2 ∪ {d}. It is easy to observe that [D′ 1 , D′ 2 ] is an LD-partition of G. Case 7: t ′ has label ⊗ and the other child of t ′ is an internal node t ′′ which has… view at source ↗
Figure 10
Figure 10. Figure 10: Case 7 3 Maximal Outerplanar graphs A mop of order 3 is a triangle, which contains twins. Hence, we consider mops of order at least 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 ther… view at source ↗
Figure 11
Figure 11. Figure 11: Subtree Tx and possible subgraph of G. corresponds to the vertex x in Tx. Since y and z are leaves in T, we have that degG(v4) = degG(v5) = 2 and degG(v3) = 4. Recall that n ≥ 6. Let H be the graph of order n ′ obtained from G by deleting the vertices v4 and v5. Since n ≥ 6, we have n ′ = n − 2 ≥ 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.… view at source ↗
Figure 12
Figure 12. Figure 12: Subtree Tx′ and possible subgraph of G. Case 1: v1, v2 ∈ D′ 1 and v3 ∈ D′ 2 . Let D1 = D′ 1∪{v5} and D2 = D′ 2∪{v4}. Now we show that each Di is an LD-set of G for i ∈ {1, 2}. Note that NG(v3) ∩ {v1, v2, v5} = {v1, v2} and NG(v4) ∩ {v1, v2, v5} = {v1, v2, v5}. Moreover, {v1, v2, v5} ⊂ D1. Therefore, D1 is an LD-set of G. Since D′ 2 is an LD-set of H, we have NH(v1) ∩ D′ 2 6= NH(v2) ∩ D′ 2 . Hence NG(v1) ∩… view at source ↗
read the original 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 vertex in $V(G) \setminus L$ has 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 \lceil\frac{5n}{8}\rceil$ 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves that every isolate-free and twin-free graph G belonging to one of four classes (distance-hereditary, maximal outerplanar, split, or co-bipartite) admits a partition of V(G) into two locating-dominating sets. This strengthens the known upper bound on the location-domination number and affirmatively resolves a question of Bousquet et al. by supplying explicit constructions for each class that rely on the standard structural characterizations together with the absence of isolates and twins.

Significance. If the proofs are correct, the result is a solid incremental contribution to the theory of locating-dominating sets. It confirms the γ_LD(G) ≤ n/2 conjecture for four important hereditary classes and supplies concrete, class-specific partitions rather than purely existential arguments. The explicit use of distance-hereditary, outerplanar, split, and co-bipartite characterizations is a clear strength.

minor comments (3)
  1. [Introduction] §1 (Introduction): the transition from the Bousquet et al. question about two locating sets to the stronger claim of two locating-dominating sets should be stated more explicitly so that readers immediately see the improvement.
  2. The proofs for the four classes are presented separately; a short unifying lemma or table summarizing the key structural property used in each case would improve readability.
  3. Ensure that every construction explicitly verifies both the dominating property and the locating property; currently some steps appear to rely on the reader filling in standard neighborhood arguments.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the recognition of its contribution to resolving the question of Bousquet et al. for the four specified hereditary classes, and the recommendation of minor revision. We appreciate the emphasis on the explicit constructions based on structural characterizations.

Circularity Check

0 steps flagged

No circularity: self-contained combinatorial proofs for graph partitions

full rationale

The manuscript proves that isolate-free twin-free graphs in four hereditary classes (distance-hereditary, maximal outerplanar, split, co-bipartite) admit a partition of V(G) into two locating-dominating sets. The arguments rely on explicit constructions that use only the standard structural characterizations of each class together with the given absence of isolates and twins. No equations define quantities in terms of themselves, no parameters are fitted to data and then relabeled as predictions, and no load-bearing step reduces to a self-citation or prior ansatz by the same authors. The central claim is established by direct case analysis and induction on the class-specific properties, remaining independent of the target partition result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard definitions of locating-dominating sets and the structural axioms of the four graph classes; no free parameters or new entities are introduced.

axioms (2)
  • standard math Standard definitions of dominating set, locating set, and locating-dominating set.
    Invoked throughout to state the main theorems.
  • domain assumption Structural properties of distance-hereditary, maximal outerplanar, split, and co-bipartite graphs.
    Used to establish the existence of the two-set partition.

pith-pipeline@v0.9.0 · 5904 in / 1305 out tokens · 66950 ms · 2026-05-19T09:17:46.660656+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    J. D. Alvarado, S. Dantas, D. Rautenbach, Dominating set s inducing large components in maximal outerplanar graphs, J. Graph Theory 88 (2018) 356–370. 12

    work page 2018

  2. [2]

    Araki, I

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

    work page 2018

  3. [3]

    Balbuena, F

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

    work page 2015

  4. [4]

    Banerjee, J

    S. Banerjee, J. Chaudhary, D. Pradhan, Unique response R oman domination: complexity and algo- rithms, Algorithmica 85 (12) (2023) 3889–3927

    work page 2023

  5. [5]

    Bousquet, Q

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

    work page 2025

  6. [6]

    Chakraborty, F

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

    work page 2024

  7. [7]

    Chakraborty, A

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

    work page arXiv 2024

  8. [8]

    Chakraborty, F

    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)

    work page 2025

  9. [9]

    M. S. Chang, S. Y. Hsieh, G. H. Chen, Dynamic programming o n distance-hereditary graphs, Proceed- ings of Seventh International Symposium on Algorithms and C omputation (ISAAC’97), Lecture Notes in Computer Science 1350 (1997) 344–353

    work page 1997

  10. [10]

    Chv´ atal, A combinatorial theorem in plane geometry , J

    V. Chv´ atal, A combinatorial theorem in plane geometry , J. Combin. Theory Ser. B 18 (1975) 39–41

    work page 1975

  11. [11]

    Claverol, A

    M. Claverol, A. Garc ´ ıa, G. Hern´ andez, C. Hernando, M.Maureso, M. Mora, J. Tejel, Metric Dimension of Maximal Outerplanar Graphs, Bull. Malays. Math. Sci. Soc . 44 (2021) 2603–2630

    work page 2021

  12. [12]

    Dorfling, J

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

    work page 2016

  13. [13]

    Foucaud, M

    F. Foucaud, M. A. Henning, Location-domination and mat ching in cubic graphs, Discrete Math. 339 (2016) 1221–1231

    work page 2016

  14. [14]

    Foucaud, M

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

    work page 2017

  15. [15]

    Foucaud, M

    F. Foucaud, M. A. Henning, C. L¨ owenstein, T. Sasse, Loc ating–dominating sets in twin-free graphs, Discrete Appl. Math. 200 (2016) 52–58

    work page 2016

  16. [16]

    Garijo, A

    D. Garijo, A. Gonz´ alez, A. M´ arquez, The difference between the metric dimension and the determining number of a graph, Appl. Math. Comput. 249 (2014) 487–501

    work page 2014

  17. [17]

    Liedloff, T

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

    work page 2008

  18. [18]

    Lobstein, O

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

    work page 2020

  19. [19]

    K. Paul, A. Sharma, A. Pandey, Exploring algorithmic so lutions for the Independent Roman Domi- nation problem in graphs. Discrete Appl. Math. 364 (2025) 14 3–152

    work page 2025

  20. [20]

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

    work page 1988