pith. sign in

arxiv: 2605.07361 · v2 · submitted 2026-05-08 · 🧮 math.CO

Independent Locating-Dominating Sets in Pseudotrees

Jos\'e C\'aceres , Ignacio M. Pelayo This is my paper

Pith reviewed 2026-05-15 06:07 UTC · model grok-4.3

classification 🧮 math.CO
keywords independent locating-dominating setstreesunicyclic graphsILD-setsdominationlocating setsgraph algorithms
0
0 comments X

The pith

Every tree and every twin-free unicyclic graph has an independent locating-dominating set.

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

An independent locating-dominating set is a collection of vertices that dominates the graph while ensuring each non-member vertex has a unique pattern of neighbors inside the set, and the set itself induces no edges. The paper proves such a set exists in every tree. It proves the same for unicyclic graphs provided the graph is twin-free, meaning no two vertices share identical open neighborhoods. The work supplies upper bounds on the minimum size of these sets, theorems showing which sizes are possible, and algorithms to construct them in both families.

Core claim

Every tree contains an ILD-set, and every twin-free unicyclic graph contains an ILD-set; the minimum cardinality of such a set admits explicit upper bounds, certain integers are realizable as this cardinality, and polynomial algorithms exist to produce one.

What carries the argument

The twin-free condition for unicyclic graphs, which removes neighborhood collisions so that an independent dominating set can also serve as a locating set.

If this is right

  • The size of the smallest ILD-set in any tree is bounded above by a function of the number of vertices.
  • Certain positive integers can be realized exactly as the ILD number of some tree or twin-free unicyclic graph.
  • Polynomial-time algorithms compute an ILD-set for every tree and every twin-free unicyclic graph.

Where Pith is reading between the lines

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

  • The twin-free condition is necessary in the unicyclic case, since the paper exhibits girth-4 graphs without ILD-sets when twins are present.
  • Similar neighborhood-uniqueness requirements may suffice for existence in graphs with a fixed number of cycles beyond one.
  • The algorithmic results open the possibility of computing ILD numbers exactly for all pseudotrees in linear time.

Load-bearing premise

Unicyclic graphs must have no two vertices with identical open neighborhoods for the existence of an ILD-set to be guaranteed.

What would settle it

A single twin-free unicyclic graph on any number of vertices that admits no independent locating-dominating set.

Figures

Figures reproduced from arXiv: 2605.07361 by Ignacio M. Pelayo, Jos\'e C\'aceres.

Figure 1
Figure 1. Figure 1: Split graphs Γ2, Γ3 and Γ4. well-known families of graphs (the solid triangle meaning that there is no ILD-graph in that family), and its relation with other domination and inde￾pendence parameters [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: There are 11 non-ILD graphs of order at most 5. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: There are 11 non-ILD graphs of order 6, without twins. [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: There are five twin-free graphs of order [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 4
Figure 4. Figure 4: There are five twin-free graphs of order [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Left: Non-ILD graph of order n = 9. Right: Non-ILD family of graphs of order n ≥ 10. 3 Trees Any tree has an ILD-set, so it is natural to begin with them to give bounds for, and compute the independent locating-dominating number whenever it is possible. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 5
Figure 5. Figure 5: Left: Non-ILD graph of order n = 9. Right: Non-ILD family of graphs of order n ≥ 10. 1 2 3 5 6 4 1 2 3 4 5 6 [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The set {2, 4, 5} is a γ l -set, meanwhile the set {1, 3, 5, 6} is an ι l -set. In [25, 27], the authors proved that for any tree of order n, n 3 < γl (T) ≤ ι l (T) ≤ 2γ l (T) − 1 However, it is possible to improve the previous upper bound in one unit, being in this case tight. Theorem 8. Let T be a tree of order n ≥ 3. Then, γ l (T) ≤ ι l (T) ≤ 2γ l (T) − 2. Proof. Clearly, as a direct consequence of both… view at source ↗
Figure 7
Figure 7. Figure 7: Every tree T contains a subtree Tˆ such that γ l (Tˆ) ≤ γ l (T) − 1 and ι l (T) ≤ ι l (Tˆ) + 2. (ii) ι l (T) ≤ ι l (Tˆ) + 2 To prove this statement, we distinguish cases. Case (1): There is a 4-vertex set {w, x, y, z} inducing the path P4, such that deg(w) ≥ 2, deg(x) = deg(y) = 2 and deg(z) = 1. (see [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Tree of order n = 3k − 2h + 1 with k leaves, with 2 ≤ h ≤ k. Left: the set of squared red vertices is a γ l -set. Right: the set of squared red vertices is an ι l -set. There exist trees for the whole range of values for γ l and ι l of the previous theorem. Theorem 9. Let r, s a pair of integers such that 2 ≤ r ≤ s ≤ 2r − 2. Then, there is a tree T such that γ l (T) = r and ι l (T) = s. Proof. Let h, k a p… view at source ↗
Figure 9
Figure 9. Figure 9: Tree of order n = 3h + 3k + 4 with h + k + 2 leaves, with 1 ≤ h and 2 ≤ k. Left: the set of squared vertices is a γ l -set. Right: the set of squared red vertices is an ι l -set [PITH_FULL_IMAGE:figures/full_fig_p014_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Unicyclic graphs of girth at most 4, containing no ILD-set. [PITH_FULL_IMAGE:figures/full_fig_p014_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Nine twin-free unicyclic graphs of girth 3. [PITH_FULL_IMAGE:figures/full_fig_p015_11.png] view at source ↗
read the original abstract

An ILD-set in a connected graph is a subset $S$ of vertices such that it is both independent and locating-dominating. The independent locating-dominating number of a graph G is the minimum cardinality of an ILD-set set of $G$. A well-known fact is that any graph with girth at least 5 has an ILD-set, but that is not clear for graphs with girth 3 and 4. In this work, we prove that there are graphs with no ILD-sets for any order $n\geq 9$ and girth 4, also showing some sufficient conditions for a bipartite graph to contain an ILD-set. Moreover, we focus our attention on trees and on unicyclic graphs, showing that every tree and every unicyclic graph contains ILD-sets, whenever in the latter case, it is twin-free. Finally, a number of bounds, realization theorems and algorithms to find an ILD-set in those families of graphs are provided.

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

1 major / 3 minor

Summary. The manuscript proves that every tree admits an independent locating-dominating (ILD) set and that every twin-free unicyclic graph does as well. It establishes non-existence of ILD-sets for certain graphs of girth 4 and order at least 9, gives sufficient conditions for bipartite graphs to contain ILD-sets, and supplies bounds, realization theorems, and algorithms for computing ILD-sets (and the ILD number) in trees and unicyclic graphs.

Significance. The existence theorems resolve the status of ILD-sets for the two simplest families containing cycles of length 3 or 4, extending the known girth-at-least-5 result. The algorithmic and extremal results provide concrete tools for computing minimal ILD-sets in pseudotrees and clarify the role of the twin-free hypothesis.

major comments (1)
  1. [Section on unicyclic graphs (sufficiency direction)] The sufficiency proof for twin-free unicyclic graphs (the central positive result) must explicitly verify that the constructed set remains locating when a tree is attached to a cycle vertex whose open neighborhood is altered by the attachment; the current argument appears to treat the cycle and pending trees separately without a joint induction or case analysis on the attachment points.
minor comments (3)
  1. [Title and abstract] The title refers to pseudotrees while the abstract and theorems treat trees and unicyclic graphs separately; add a sentence clarifying whether pseudotree is used synonymously with unicyclic graph or denotes a broader class.
  2. [Algorithms section] Notation for the independent locating-dominating number is introduced but not consistently used in the algorithmic section; adopt a single symbol (e.g., i_L(G)) throughout.
  3. [Non-existence results] The non-existence examples for girth-4 graphs of order >=9 are stated but the smallest explicit counterexample (order 9) should be drawn or tabulated to allow immediate verification.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying a point where the exposition of the sufficiency proof for twin-free unicyclic graphs can be strengthened. We will revise the manuscript to incorporate an explicit joint analysis of the cycle and attached trees.

read point-by-point responses

  1. Referee: [Section on unicyclic graphs (sufficiency direction)] The sufficiency proof for twin-free unicyclic graphs (the central positive result) must explicitly verify that the constructed set remains locating when a tree is attached to a cycle vertex whose open neighborhood is altered by the attachment; the current argument appears to treat the cycle and pending trees separately without a joint induction or case analysis on the attachment points.

    Authors: We agree that an explicit verification strengthens the argument. In the revised version we will insert a short case analysis immediately after the construction: when a tree T is attached at a cycle vertex v, the ILD-set S is formed by taking the ILD-set of the cycle (which is independent and locating on the cycle) union an ILD-set of T chosen so that the unique neighbor of the attachment edge in S (if any) distinguishes the root of T from all other vertices. Because the graph is twin-free, no vertex in T can share the same open neighborhood in S with a vertex on the cycle or in another attached tree; the locating property on the cycle is preserved since attachments only enlarge neighborhoods of cycle vertices already dominated by S, and the independence of S is immediate from the separate choices. This joint check will be written out for the three possible local configurations at v (v in S, v not in S but dominated by a cycle neighbor in S, or v dominated only by the attachment). revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes its central claims—that every tree admits an ILD-set and every twin-free unicyclic graph does as well—via direct combinatorial constructions and case analysis on the structure of trees and unicyclic graphs. These arguments rely on explicit vertex selections that satisfy the independent, dominating, and locating conditions simultaneously, without presupposing the target quantity in the definitions or reducing any existence statement to a fitted parameter or self-citation chain. The twin-free hypothesis is introduced explicitly as a necessary restriction for the unicyclic case, and counterexamples for girth-4 graphs are handled separately. No load-bearing step collapses to a renaming, ansatz smuggling, or uniqueness theorem imported from the authors' prior work; the derivation remains self-contained against the graph-theoretic definitions provided.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies exclusively on the standard axiomatic framework of graph theory (undirected simple graphs, adjacency, neighborhoods) with no additional free parameters, ad-hoc axioms, or postulated entities.

axioms (1)
  • standard math Standard definitions of independent set, dominating set, locating set, and the derived notion of independent locating-dominating set.
    All results are proved from these classical definitions without introducing new primitives.

pith-pipeline@v0.9.0 · 5472 in / 1126 out tokens · 38222 ms · 2026-05-15T06:07:29.063786+00:00 · methodology

Review history (2 revisions) →

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

29 extracted references · 29 canonical work pages

  1. [1]

    On domination and independent domi- nation numbers of a graph

    Allan, R.B., Laskar, R., 1978. On domination and independent domi- nation numbers of a graph. Discrete Math. 23, 73–76

    work page 1978

  2. [2]

    Theory of Graphs and its Applications

    Berge, C., 1962. Theory of Graphs and its Applications. John Wiley & Sons, New York, NY

    work page 1962

  3. [3]

    Identifying and locating-dominating codes on chains and cycles

    Bertrand, N., Charon, I., Hudry, O., Lobstein, A., 2004. Identifying and locating-dominating codes on chains and cycles. European J. Combin. 25, 969–987

    work page 2004

  4. [4]

    Independent domination in trees

    Beyer, T., Proskurowski, A., T., Hedetniemi, S., Mitchell, S., 1977. Independent domination in trees. Congress. Numer. XIX, 321–328

    work page 1977

  5. [5]

    Character- izations of trees with unique minimum locating-dominating sets

    Blidia, M., Chellali, M., Lounes, R., Maffray, F., 2011. Character- izations of trees with unique minimum locating-dominating sets. J. Combin. Math. Combin. Comput. 76, 225–232

    work page 2011

  6. [6]

    Locating-domination and identifying codes in trees

    Blidia, M., Chellali, M., Maffray, F., Moncel, J., Semri, A., 2007. Locating-domination and identifying codes in trees. Australas. J. Com- bin. 39, 219–232

    work page 2007

  7. [7]

    Graph-theoretic parameters con- cerning domination, independence, and irredundance

    Bollob´ as, B., Cockayne, E.J., 1979. Graph-theoretic parameters con- cerning domination, independence, and irredundance. J. Graph Theory 3, 241–249

    work page 1979

  8. [8]

    A new lower bound for the independent domination number of a tree

    Cabrera-Mart´ ınez, A., 2023. A new lower bound for the independent domination number of a tree. RAIRO Oper. Res. 4, 1951–1956

    work page 2023

  9. [9]

    Locating dominating codes: Bounds and extremal cardinalities

    C´ aceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., 2013. Locating dominating codes: Bounds and extremal cardinalities. Appl. Math. Comput. 220, 38–45

    work page 2013

  10. [10]

    Distinct sizes of max- imal independent sets on graphs with restricted girth

    Cappelle, M., Nascimento, J., Santos, V., 2024. Distinct sizes of max- imal independent sets on graphs with restricted girth. RAIRO Oper. Res. 58, 2379–2391. 19

    work page 2024

  11. [11]

    Graphs and digraphs

    Chartrand, G., Lesniak, L., Zhang, P., 2016. Graphs and digraphs. CRC Press, Boca Raton, FL

    work page 2016

  12. [12]

    On locating-domination in graphs

    Chellali, M., Mimouni, M., Slater, P.J., 2010. On locating-domination in graphs. Discuss. Math. Graph Theory 30, 223–235

    work page 2010

  13. [13]

    Independence graphs

    Cockayne, E.J., Hedetniemi, S.T., 1974. Independence graphs. Congr. Numer. X, 471–491

    work page 1974

  14. [14]

    Towards a theory of domina- tion in graphs

    Cockayne, E.J., Hedetniemi, S.T., 1977. Towards a theory of domina- tion in graphs. Networks 7, 247–261

    work page 1977

  15. [15]

    The number of locat- ing independent dominating set on generalized corona product graphs

    Dafik, Agustin, I.H., Wardani, D.A.R., 2022. The number of locat- ing independent dominating set on generalized corona product graphs. Advances in Mathematics: Scientific Journal 9, 4873–4891

    work page 2022

  16. [16]

    A bound on the independent domination number of a tree

    Favaron, O., 1992. A bound on the independent domination number of a tree. Vishwa Internat. J. Graph Theory 1, 19–27

    work page 1992

  17. [17]

    Independent domination in graphs: a survey and recent results

    Goddard, W., Henning, M.A., 2013. Independent domination in graphs: a survey and recent results. Discrete Math. 313, 839–854

    work page 2013

  18. [18]

    Fundamentals of Domi- nation in Graphs

    Haynes, T., Hedetniemi, S., Slater, P.J., 1998. Fundamentals of Domi- nation in Graphs. Marcel Dekker, New York, NY

    work page 1998

  19. [19]

    Nordhaus-gaddum bounds for locating domination

    Hernando, C., Mora, M., Pelayo, I.M., 2014. Nordhaus-gaddum bounds for locating domination. European J. Combin. 36, 1–6

    work page 2014

  20. [20]

    Locating domination in bipartite graphs and their complements

    Hernando, C., Mora, M., Pelayo, I.M., 2019. Locating domination in bipartite graphs and their complements. Discrete Appl. Math. 263, 195–203

    work page 2019

  21. [21]

    Watching systems, identifying, locating-dominating and discriminating codes in graphs

    Jean, D., 2023. Watching systems, identifying, locating-dominating and discriminating codes in graphs. https://dragazo.github.io/bibdom/main.pdf

    work page 2023

  22. [22]

    Independent location domination number of graphs

    Kaewperm, P., Kalarkop, D.A., Kaemawichanurat, P., . Independent location domination number of graphs. Submitted to CCO

    work page

  23. [23]

    Locating-domination and identification

    Lobstein, A., Hudry, O., Charon, I., 2020. Locating-domination and identification. Dev. Math 64, 251–299

    work page 2020

  24. [24]

    Locating-domination and identification

    Ore, O., 1962. Locating-domination and identification. Amer. Math. Soc. Transl. 38, 206–212. 20

    work page 1962

  25. [25]

    Domination and location in acyclic graphs

    Slater, P.J., 1987. Domination and location in acyclic graphs. Networks 17, 55–64

    work page 1987

  26. [26]

    Dominating and reference sets in a graph

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

    work page 1988

  27. [27]

    Independent locating-dominating sets and identifying codes in graphs

    Slater, P.J., Sewell, J., 2018. Independent locating-dominating sets and identifying codes in graphs. J. Combin. Math. Combin. Comput. 104, 261–272

    work page 2018

  28. [28]

    On locating independent domination number of amalgamation graphs

    Wardani, D.A.R., Dafik, Agustin, I.H., Kurniawati, E.Y., 2017. On locating independent domination number of amalgamation graphs. J. Phys.: Conf. Series 943, 012027

    work page 2017

  29. [29]

    Independent locating-dominating sets in some graphs constructed from cycles

    Xavier Lemos, D., Cappelle, M.R., Martins Coelho, E.M., Foulds, L.R., J., L.H., 2025. Independent locating-dominating sets in some graphs constructed from cycles. Mat. Contemp. . 21

    work page 2025