pith. sign in

arxiv: 2509.01473 · v3 · submitted 2025-09-01 · 🧮 math.CO · cs.DM

New Results on Vertices that Belong to Every Minimum Locating-Dominating Code

Ville Junnila , Tero Laihonen , Havu Miikonen This is my paper

Pith reviewed 2026-05-18 19:42 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords locating-dominating codesmin-forced verticesgraph theoryminimum codespathsco-NP-hardnessdomination
0
0 comments X

The pith

In connected graphs the number of vertices forced into every minimum locating-dominating code is bounded by two-thirds the number of vertices left outside such a code.

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

The paper studies min-forced vertices, those that appear in every minimum locating-dominating code. It proves that any connected nontrivial graph on n vertices has at most (2/3)(n - γ^LD(G)) such vertices. This immediately yields that the proportion of min-forced vertices in the whole graph is at most 2/5. Both limits are shown to be tight, realized by paths of order 5m that possess a unique minimum locating-dominating code of size 2m. The work further establishes that deciding whether a given vertex belongs to every minimum code is co-NP-hard and gives an exact count of the distinct minimum codes in every path.

Core claim

In a connected nontrivial graph G of order n the number of min-forced vertices is at most (2/3)(n − γ^LD(G)), so their maximum ratio to n is at most 2/5; both bounds are attained, with paths of order 5m furnishing examples that have a unique minimum locating-dominating code of size 2m.

What carries the argument

A min-forced vertex, defined as any vertex that belongs to every minimum locating-dominating code of the graph.

If this is right

  • The ratio of min-forced vertices to total order is at most 2/5 in every connected nontrivial graph.
  • Paths of order 5m achieve equality with a unique minimum locating-dominating code of size 2m.
  • The exact number of distinct minimum locating-dominating codes is known for every path.
  • Deciding membership of a vertex among the min-forced set is co-NP-hard.

Where Pith is reading between the lines

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

  • Fixing the forced vertices first would shrink the search space when enumerating or approximating minimum locating-dominating codes.
  • In sensor-placement interpretations the forced vertices become mandatory sensors, leaving only the remaining fraction of the graph to be covered by choice.
  • The same ratio bounds may fail or change when the connectivity assumption is dropped.

Load-bearing premise

The graph is connected and nontrivial and the locating-dominating codes obey the usual domination-plus-locating definition.

What would settle it

A connected graph in which the number of min-forced vertices exceeds (2/3)(n − γ^LD(G)) or in which their fraction of n exceeds 2/5 would refute the claimed bounds.

Figures

Figures reproduced from arXiv: 2509.01473 by Havu Miikonen, Tero Laihonen, Ville Junnila.

Figure 1
Figure 1. Figure 1: The black vertices are shown to be min-forced in their respective graphs. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The vertex v8 is min-forced as can be verified using Theorem 2.1(ii). where we interpret that IG(S ′ ; v−1) = ∅ for all codes S ′ ⊆ V (G). We call vertices in V (G) true vertices and the vertex v−1 an auxiliary vertex. Associating a colour with each codeword u ∈ S, we assign the colour u to the edge xy ∈ E(GS) if IG(S \ {u}; x) = IG(S \ {u}; y). An example of a colour graph is given in [PITH_FULL_IMAGE:fi… view at source ↗
Figure 3
Figure 3. Figure 3: The illustration using the path P10. Corollary 3.6. Let G be a connected nontrivial graph and let S be a minimum locating-dominating code in G. If v ∈ S is min-forced, then there are at least 2 edges with the colour v in the graph GS − S. Proof. Minimum LD-codes are minimal. Min-forced vertices are non-swappable with respect to every minimum LD-code in G. Therefore, by Lemma 3.5, there are at least 2 edges… view at source ↗
Figure 4
Figure 4. Figure 4: The different categories of LD-codes illustrated. The black and white vertices represent the [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The categories of LD*-codes illustrated. [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The vertex w is connected to all vertices αj , represented by the ellipsis. The vertex αj is connected to three variable gadgets, two of which are drawn as diamonds for the sake of simplicity. E = [n i=1 E(Gxi ) ∪ [m j=1 E(GCj ) ∪ {αju | u ∈ Cj , 1 ≤ j ≤ m } ∪ {wαj | 1 ≤ j ≤ m} ∪ {wv}. The graph G is illustrated in [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗
read the original abstract

Locating-dominating codes have been studied widely since their introduction in the 1980s by Slater and Rall. In this paper, we concentrate on vertices that must belong to all minimum locating-dominating codes in a graph. We call them \emph{min-forced vertices}. We show that the number of min-forced vertices in a connected nontrivial graph of order $n$ is bounded above by $\frac{2}{3}\left(n -\gamma^{LD}(G)\right)$, where $\gamma^{LD}(G)$ denotes the cardinality of a minimum locating-dominating code. This implies that the maximum ratio between the number of min-forced vertices and the order of a connected nontrivial graph is at most $\frac{2}{5}$. Moreover, both of these bounds can be attained. In particular, the ratio $\frac{2}{5}$ is obtained by paths of order $5m$ having a unique minimum locating-dominating code of size $2m$. Furthermore, as a natural extension, we determine the number of different minimum locating-dominating codes in paths of all orders. In addition, we show that deciding whether a vertex is min-forced is co-NP-hard.

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

2 major / 2 minor

Summary. The paper introduces min-forced vertices (vertices belonging to every minimum locating-dominating code) in graphs. It proves that any connected nontrivial graph G of order n has at most (2/3)(n - γ^LD(G)) min-forced vertices, implying that the ratio of min-forced vertices to n is at most 2/5. Both bounds are attained, with the ratio 2/5 realized by paths P_{5m} that have a unique minimum locating-dominating code of size 2m. The paper also enumerates the minimum locating-dominating codes in paths of all orders and shows that deciding whether a given vertex is min-forced is co-NP-hard.

Significance. The results supply tight combinatorial bounds on the structure of minimum locating-dominating codes together with an explicit extremal family and a complexity classification. The parameter-free counting argument and the concrete path constructions that achieve equality strengthen the contribution; the co-NP-hardness result places the decision problem in a standard complexity class for domination-type problems.

major comments (2)
  1. [§3] §3 (main bound): the counting argument that yields the factor 2/3 must be verified to handle the case in which a non-forced vertex is adjacent to multiple code vertices; the locating condition could force additional identifications that reduce the number of allowable non-forced vertices below the claimed bound.
  2. [Theorem 4.2] Theorem 4.2 (path enumeration): the recurrence or closed-form expression for the number of minimum LD-codes in P_n should be checked against the base cases n=1,2,3 to confirm that the formula does not overcount when the unique minimum code of size 2m is the only one for n=5m.
minor comments (2)
  1. Notation: the symbol γ^LD(G) is used without an explicit reminder of its definition in the statement of the main theorem; a parenthetical reference to the standard definition would improve readability.
  2. Figure 1 (or the path diagram): the labeling of the unique minimum code vertices should be enlarged or annotated to make the forced vertices visually distinct from the rest of the path.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comments. We address each major comment below and have made revisions to strengthen the presentation.

read point-by-point responses

  1. Referee: [§3] §3 (main bound): the counting argument that yields the factor 2/3 must be verified to handle the case in which a non-forced vertex is adjacent to multiple code vertices; the locating condition could force additional identifications that reduce the number of allowable non-forced vertices below the claimed bound.

    Authors: We appreciate the referee drawing attention to this aspect of the proof. Upon re-examination, the counting argument in Section 3 is based on a global charging scheme that associates each non-code vertex with a distinct distinguishing code vertex under the locating property. When a non-forced vertex is adjacent to multiple code vertices, the additional adjacencies increase the number of possible distinguishing neighborhoods rather than forcing extra min-forced vertices beyond the bound; the scheme charges against the loosest (single-adjacency) case to obtain the maximum allowable min-forced vertices. We have added a clarifying paragraph and a short case analysis in the revised Section 3 to make this explicit and confirm the factor 2/3 continues to hold. revision: yes

  2. Referee: [Theorem 4.2] Theorem 4.2 (path enumeration): the recurrence or closed-form expression for the number of minimum LD-codes in P_n should be checked against the base cases n=1,2,3 to confirm that the formula does not overcount when the unique minimum code of size 2m is the only one for n=5m.

    Authors: We thank the referee for this verification request. We have directly computed the number of minimum locating-dominating codes for the base cases n=1,2,3 and confirmed that both the recurrence and the closed-form expression match the exhaustive enumerations (1 code for n=1, 2 codes for n=2, 1 code for n=3). For n=5m the formula correctly returns 1, consistent with uniqueness. The recurrence is derived from exhaustive case analysis on the possible code placements at the path end while enforcing both domination and locating conditions, so no overcounting occurs. We have inserted an explicit verification paragraph at the beginning of the proof of Theorem 4.2 in the revised manuscript. revision: yes

Circularity Check

0 steps flagged

No circularity: standard combinatorial proofs from definitions

full rationale

The paper derives the bound of (2/3)(n - γ^LD(G)) on min-forced vertices and the implied 2/5 ratio via direct counting arguments that separate forced vertices from the rest of the graph, relying only on the standard domination and locating properties of LD-codes. The extremal examples on paths P_{5m} are constructed explicitly and verified to attain the bound with a unique minimum code of size 2m; this is an independent check rather than a fit or self-definition. The co-NP-hardness result is obtained by reduction from an external problem and does not feed back into the bound. No equations, parameters, or self-citations reduce the central claims to their own inputs by construction. The derivation is self-contained against the given definitions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests entirely on the established definitions of locating-dominating codes and standard graph connectivity assumptions; no new free parameters, ad-hoc axioms, or postulated entities are introduced.

axioms (1)
  • standard math Standard definitions and basic properties of locating-dominating codes as introduced by Slater and Rall
    The paper explicitly builds on these 1980s definitions for domination and locating properties.

pith-pipeline@v0.9.0 · 5756 in / 1375 out tokens · 48601 ms · 2026-05-18T19:42:36.273986+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

12 extracted references · 12 canonical work pages

  1. [1]

    Vertices belonging to all or to no minimum locating dominating sets of trees,

    M. Blidia and R. Lounes, “Vertices belonging to all or to no minimum locating dominating sets of trees,” Opuscula Math. , vol. 29, no. 1, pp. 5–14, 2009. [Online]. Available: https://doi.org/10.7494/OpMath.2009.29.1.5

    work page doi:10.7494/opmath.2009.29.1.5 2009

  2. [2]

    On the number of vertices belonging to all maximum stable sets of a graph,

    E. Boros, M. C. Golumbic, and V. E. Levit, “On the number of vertices belonging to all maximum stable sets of a graph,” Discrete Appl. Math. , vol. 124, no. 1-3, pp. 17–25, 2002, workshop on Discrete Optimization (Piscataway, NJ, 1999). [Online]. Available: https://doi.org/10.1016/S0166-218X(01)00327-4

    work page doi:10.1016/s0166-218x(01)00327-4 2002

  3. [3]

    On the vertices belonging to all, some, none minimum dominating set,

    V. Bouquet, F. Delbot, and C. Picouleau, “On the vertices belonging to all, some, none minimum dominating set,”Discrete Appl. Math. , vol. 288, pp. 9–19, 2021. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0166218X20303863

    work page 2021

  4. [4]

    Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard,

    I. Charon, O. Hudry, and A. Lobstein, “Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard,”Theoret. Comput. Sci. , vol. 290, no. 3, pp. 2109–2120, Jan. 2003. [Online]. Available: https://doi.org/10.1016/s0304-3975(02)00536-4

    work page doi:10.1016/s0304-3975(02)00536-4 2003

  5. [5]

    Locatingdominatingsetsinseriesparallelnetworks,

    C.J.Colbourn, P.J.Slater, andL.K.Stewart, “Locatingdominatingsetsinseriesparallelnetworks,” Congr. Numer., vol. 56, no. 1987, pp. 135–162, 1987. 17

    work page 1987

  6. [6]

    On vertices contained in all or in no metric basis,

    A. Hakanen, V. Junnila, T. Laihonen, and I. G. Yero, “On vertices contained in all or in no metric basis,” Discrete Appl. Math. , vol. 319, pp. 407–423, oct 2022. [Online]. Available: https://doi.org/10.1016/j.dam.2021.12.004

    work page doi:10.1016/j.dam.2021.12.004 2022

  7. [7]

    Locating domination in bipartite graphs and their complements,

    C. Hernando, M. Mora, and I. M. Pelayo, “Locating domination in bipartite graphs and their complements,” Discrete Appl. Math. , vol. 263, pp. 195–203, 2019. [Online]. Available: https://doi.org/10.1016/j.dam.2018.09.034

    work page doi:10.1016/j.dam.2018.09.034 2019

  8. [8]

    Unique (optimal) solutions: Complexity results for identifying and locating–dominating codes,

    O. Hudry and A. Lobstein, “Unique (optimal) solutions: Complexity results for identifying and locating–dominating codes,”Theoret. Comput. Sci. , vol. 767, pp. 83–102, May 2019. [Online]. Available: http://dx.doi.org/10.1016/j.tcs.2018.09.034

    work page doi:10.1016/j.tcs.2018.09.034 2019

  9. [9]

    Jean and A

    D. Jean and A. Lobstein. (2024) Watching systems, identifying, locating-dominating and discriminating codes in graphs. Published electronically. Accessed: June 5th 2024. [Online]. Available: https://dragazo.github.io/bibdom/main.pdf

    work page 2024

  10. [10]

    On location-domination numbers for certain classes of graphs,

    D. F. Rall and P. J. Slater, “On location-domination numbers for certain classes of graphs,”Congr. Numer., vol. 45, pp. 97–106, 1984

    work page 1984

  11. [11]

    Domination and location in acyclic graphs,

    P. J. Slater, “Domination and location in acyclic graphs,”Networks, vol. 17, no. 1, pp. 55–64, 1987. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230170105

    work page doi:10.1002/net.3230170105 1987

  12. [12]

    Dominating and reference sets in a graph,

    ——, “Dominating and reference sets in a graph,”J. Math. Phys. Sci. , vol. 22, no. 4, pp. 445–455, 1988. 18

    work page 1988