Pith. sign in

REVIEW 2 minor 43 references

Optimal local identifying and local locating-dominating codes

T0 review · 0 major / 2 minor · reviewed 2026-05-24 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Local 1-identifying codes in the hypercube have asymptotically the same minimal density as covering codes.

desk verdict The paper defines local r-identifying codes and shows they match covering-code density asymptotically in hypercubes while hitting optimal densities in seven of eight grid cases. read the letter →

arxiv 2302.13351 v3 submitted 2023-02-26 cs.DM math.CO

Pyry Herva , Tero Laihonen , Tuomo Lehtilä This is my paper · ORCID
classification cs.DMmath.CO
keywords localidentifyingcodeslocating-dominatinghypercubescoveringgridgraphscodedensityasymptoticboundsoptimalconstructions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper establishes that local 1-identifying codes, which ensure each vertex has a unique intersection pattern with the code inside its closed neighborhood, can be built with sizes that match the asymptotic lower bounds known for ordinary covering codes. Matching upper bounds come from explicit linear constructions, showing the added local distinction costs nothing in the limit. In the square, hexagonal, triangular, and king grids the authors supply constructions for both local identifying and local locating-dominating codes and prove that seven of the eight achieve the lowest possible density. A sympathetic reader would care because these results indicate that the extra local uniqueness property can be obtained essentially for free once a covering code already exists.

What carries the argument

Local 1-identifying code: a subset C such that the sets N[v] ∩ C are distinct for every pair of vertices v.

What would settle it

An explicit construction or lower-bound argument showing that the ratio of minimal local 1-identifying code size to minimal covering code size in the hypercube remains bounded away from 1 as dimension tends to infinity.

Watch

Extended reading notes

Core claim

The minimal cardinality of a local 1-identifying code in the n-dimensional binary hypercube is asymptotically equal to the minimal cardinality of a covering code; the ratio of the two quantities tends to one. The same constructions also yield seven density-optimal local 1-identifying and local 1-locating-dominating codes among the eight grid families examined.

Load-bearing premise

The local uniqueness condition on neighborhood intersections can always be satisfied by a code whose size remains within a factor approaching one of the size of a minimal covering code.

Editorial extensions

If this is right

  • The overhead of enforcing local identification vanishes asymptotically in the hypercube.
  • Linear codes achieve the matching upper bounds for local 1-identifying codes.
  • Seven of the eight presented grid constructions are proven to have the smallest possible density.
  • Exact optimal sizes are determined for small-dimensional hypercubes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The negligible overhead may extend to other regular graphs where covering codes are already dense.
  • Similar constructions could be tested for r greater than 1 to check whether the asymptotic tightness persists.
  • The linear-code method might be adapted to produce local locating-dominating codes in the hypercube as well.
  • Applications in distributed sensor placement could exploit the fact that local distinction adds almost no extra sensors.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The paper introduces local r-identifying and local r-locating-dominating codes as variants of standard identifying and locating-dominating codes. For the binary hypercube, it derives asymptotically tight lower and upper bounds on the size of optimal local 1-identifying codes, showing that the cost of enforcing the local condition over ordinary covering codes is negligible; it also gives explicit optimal constructions for small n and obtains the upper bound via a linear code. For the infinite square, hexagonal, triangular, and king grids it determines densities of optimal local 1-identifying and local 1-locating-dominating codes and proves that seven of the eight presented constructions achieve those optimal densities.

Significance. If the bounds and optimality proofs hold, the work is significant because it establishes that local identification can be realized at asymptotically the same density as ordinary covering codes, which is useful for applications in network fault detection and locating. The explicit linear-code construction and the seven optimal grid densities supply concrete, usable benchmarks for further combinatorial coding research.

minor comments (2)
  1. [Abstract] Abstract: the statement that seven out of eight constructions are optimal would be clearer if the single non-optimal construction were identified by name or grid type.
  2. The definitions of the local codes would benefit from a short worked example (e.g., a small hypercube or grid fragment) immediately after the formal definition to illustrate the radius-r neighborhood condition.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, the assessment of significance, and the recommendation of minor revision. The report correctly captures the main contributions on local r-identifying and local r-locating-dominating codes, the asymptotically tight bounds for hypercubes, the linear-code construction, and the optimality results for seven of the eight grid densities.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity in derivation chain

full rationale

The paper defines local r-identifying and local r-locating-dominating codes as independent variants of existing covering codes. Asymptotically tight bounds on hypercube sizes are obtained via combinatorial counting arguments that do not reduce to fitted parameters or self-referential definitions. Grid densities rely on explicit constructions whose optimality is shown by matching independent lower bounds in seven of eight cases. No load-bearing self-citations, ansatzes smuggled via prior work, or renamings of known results appear in the stated logic. The central claims rest on self-contained combinatorial derivations.

Assumptions & free parameters 0 free parameters · 1 assumptions · 2 invented entities

The central claims rest on new definitions of the local codes together with combinatorial arguments on hypercubes and grids; no numerical fitting or invented physical entities are used.

assumptions (1)
  • standard math Standard definitions and basic properties of r-identifying codes and r-locating-dominating codes in graphs
    The paper states that the new local codes are derived from these existing objects.
invented entities (2)
  • local r-identifying code
    purpose: A variant of identifying codes in which identification occurs only inside the closed r-neighborhood of each vertex
    Newly introduced class whose minimum size is the object of study.
  • local r-locating-dominating code
    purpose: A variant of locating-dominating codes with the same local identification requirement
    Newly introduced class whose minimum density is studied in grids.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal local identifying and local locating-dominating codes." pith.science (2026). https://pith.science/paper/2302.13351

@misc{pith2026230213351,
  author       = {Pith},
  title        = {Pith review of: Optimal local identifying and local locating-dominating codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2302.13351}},
  note         = {Machine review of arXiv:2302.13351}
}
abstract

We introduce two new classes of covering codes in graphs for every positive integer $r$. These new codes are called local $r$-identifying and local $r$-locating-dominating codes and they are derived from $r$-identifying and $r$-locating-dominating codes, respectively. We study the sizes of optimal local 1-identifying codes in binary hypercubes. We obtain lower and upper bounds that are asymptotically tight. Together the bounds show that the cost of changing covering codes into local 1-identifying codes is negligible. For some small $n$ optimal constructions are obtained. Moreover, the upper bound is obtained by a linear code construction. Also, we study the densities of optimal local 1-identifying codes and local 1-locating-dominating codes in the infinite square grid, the hexagonal grid, the triangular grid, and the king grid. We prove that seven out of eight of our constructions have optimal densities.

Figures

Figures reproduced from arXiv: 2302.13351 by the authors.

Figure 1
Figure 1. A graph that admits a local 2-identifying code but d [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Illustration of the hierarchy between different c [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. The darkened vertices form a (non-optimal) coveri [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: (0, 0) (a) The square grid S (0, 0) (b) The hexagonal grid H (0, 0) (c) The triangular grid T (0, 0) (d) The king grid K [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]
Figure 5
Figure 5. Figure 5: Local location-domination in the square and hexag [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]
Figure 6
Figure 6. Figure 6: Local identifying codes in the square and hexagona [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]
Figure 7
Figure 7. Figure 7: Local identifying and locating-dominating codes [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]
Figure 8
Figure 8. Figure 8: Constellations in the king grid. The edges have bee [PITH_FULL_IMAGE:figures/full_fig_p022_8.png]
Figure 9
Figure 9. Figure 9: Constellations in the king grid. The edges have bee [PITH_FULL_IMAGE:figures/full_fig_p024_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages

  1. [1]

    On the metric dimension of a graph

    Harary F, Melter RA. On the metric dimension of a graph. Ars Combin., 1976. 2:191–195

    work page 1976

  2. [2]

    Leaves of trees

    Slater PJ. Leaves of trees. In: Proceedings of the Sixth S outheastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congr. Numer., No. XIV . Utilitas Math., Winnipeg, Man., 1975 pp. 549–559

    work page 1975

  3. [3]

    On a new class of codes for identifying vertices in graphs

    Karpovsky MG, Chakrabarty K, Levitin LB. On a new class of codes for identifying vertices in graphs. IEEE Trans. Inf. Theory, 1998. IT -44:599–611. doi:10.1109/18.661507

    work page doi:10.1109/18.661507 1998

  4. [4]

    On location-domination numbers for c ertain classes of graphs

    Rall DF, Slater PJ. On location-domination numbers for c ertain classes of graphs. Congr . Numer ., 1984. 45:97–106

    work page 1984

  5. [5]

    Dominating and reference sets in a graph

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

    work page 1988

  6. [6]

    On local metric dimensions of graphs

    Okamoto F, Phinezy B, Zhang P . On local metric dimensions of graphs. J. Combin. Math. Combin. Comput., 2010. 72:243–259

    work page 2010

  7. [7]

    The local metric dimension of a graph

    Okamoto F, Phinezy B, Zhang P . The local metric dimension of a graph. Math. Bohem., 2010. 135(3):239–

    work page 2010

  8. [8]

    doi:10.21136/MB.2010.140702

    ISSN:0862-7959. doi:10.21136/MB.2010.140702

    work page doi:10.21136/mb.2010.140702 2010

Show all 43 references
  1. [9]

    Local metric dimension of graphs : Generalized hierarchical products and some applications

    Klavˆ zar S, Tavakoli M. Local metric dimension of graphs : Generalized hierarchical products and some applications. Appl. Math. Comput. , 2020. 364:124676. doi:10.1016/j.amc.2019.124676

    2020 doi

  2. [10]

    Local identifying and local locatin g-dominating codes in graphs

    Herva P , Laihonen T. Local identifying and local locatin g-dominating codes in graphs. Pro- ceedings of the Sixth Russian-Finnish Symposium on Discret e Mathematics , 2021. URL http://urn.fi/URN:ISBN:978-952-12-4113-0

    2021

  3. [11]

    Lokaali identifiointi graafeissa (in Finnish)

    Herva P . Lokaali identifiointi graafeissa (in Finnish) . Master’s thesis, University of Turku, 2020

    2020

  4. [12]

    Watching systems, identifying, loc ating-dominating and discriminating codes in graphs

    Jean D, Lobstein A. Watching systems, identifying, loc ating-dominating and discriminating codes in graphs. https://dragazo.github.io/bibdom/main.pdf

  5. [13]

    The NP-completeness of Stein er tree and dominating set for chordal bipartite graphs

    M¨ uller H, Brandst¨ adt A. The NP-completeness of Stein er tree and dominating set for chordal bipartite graphs. Theor . Comput Sci., 1987. 53(2-3):257–265. doi:10.1016/0304-3975(87)90067-3

    1987 doi

  6. [14]

    On identifying codes

    Cohen GD, Honkala IS, Lobstein A, Z´ emor G. On identifying codes. In: Codes and Association Schemes. Springer, 1999 pp. 97–109. doi:10.1090/dimacs/056/07

    1999 doi

  7. [15]

    Fault-tolerant locating dominating sets

    Slater PJ. Fault-tolerant locating dominating sets. Discrete Math. , 2002. 249:179–189. doi:10.1016/ S0012-365X(01)00244-8

    2002

  8. [16]

    Nonlocal metric dimension of grap hs

    Klavˇ zar S, Kuziak D. Nonlocal metric dimension of grap hs. Bull. Malaysian Math. Sci. Soc. , 2023. 46(2):66. doi:10.1007/s40840-022-01459-x

    2023 doi

  9. [17]

    New b ounds and constructions for neighbor- locating colorings of graphs

    Chakraborty D, Foucaud F, Nandi S, Sen S, Supraja D. New b ounds and constructions for neighbor- locating colorings of graphs. In: Algorithms and Discrete A pplied Mathematics: 9th International Con- ference, CALDAM 2023, Gandhinagar, India, February 9–11, 2 023, Proceedings. ...

    2023 doi

  10. [18]

    The lo cating-chromatic number of a graph

    Chartrand G, Erwin D, Henning M, Slater P , Zhang P . The lo cating-chromatic number of a graph. Bull. Inst. Combin. Appl , 2002. 36(89):101

    2002

  11. [19]

    Locally identifying coloring of graphs

    Esperet L, Gravier S, Montassier M, Ochem P , Parreau A. Locally identifying coloring of graphs. Electron. J. Comb., 2012. 19(2):P40. doi:10.37236/2417

    2012 doi

  12. [20]

    The RED-BLUE SEP ARA TION problem on graphs

    Dev SR, Dey S, Foucaud F, Klasing R, Lehtil¨ a T. The RED-BLUE SEP ARA TION problem on graphs. In: Combinatorial Algorithms: 33rd International Workshop, I WOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings. Springer, 2022 pp. 285–298. doi:10.1007/978 -3-031-06678-8 21

    2022 doi

  13. [21]

    The RED-B LUE SEP ARA TION problem on graphs

    Dev SR, Dey S, Foucaud F, Klasing R, Lehtil¨ a T. The RED-B LUE SEP ARA TION problem on graphs. Theor . Comput. Sci., 2023. 970. doi:10.1016/j.tcs.2023.114061

    2023 doi

  14. [22]

    New identifying c odes in the binary Hamming space

    Charon I, Cohen G, Hudry O, Lobstein A. New identifying c odes in the binary Hamming space. Eur . J. Comb., 2010. 32:491–501. doi:10.1016/j.ejc.2009.03.032

    2010 doi

  15. [23]

    On locating-dominating codes in binary Hamming spaces

    Honkala I, Laihonen T, Ranto S. On locating-dominating codes in binary Hamming spaces. Discrete Math. Theor . Comput. Sci., 2004. 6(2). doi:10.46298/dmtcs.322

    2004 doi

  16. [24]

    Identifying and locating-dominating codes in binary Hamming spaces

    Ranto S. Identifying and locating-dominating codes in binary Hamming spaces. Turku Centre for Com- puter Science, 2007

    2007

  17. [25]

    Improved lower boundfor locating-dominating codes in binary Hamming spaces

    Junnila V , Laihonen T, Lehtil¨ a T. Improved lower boundfor locating-dominating codes in binary Hamming spaces. Des. Codes Cryptogr ., 2022. 90(1):67–85. doi:10.1007/s10623-021-00963-8

    2022 doi

  18. [26]

    Bounds on identifying code s

    Blass U, Honkala I, Litsyn S. Bounds on identifying code s. Discrete Math. , 2001. 241:119–128. doi:10.1016/S0012-365X(01)00113-3

    2001 doi

  19. [27]

    New bounds on binary identif ying codes

    Exoo G, Laihonen T, Ranto S. New bounds on binary identif ying codes. Discret. Appl. Math. , 2008. 156(12):2250–2263. doi:10.1016/j.dam.2007.09.017

    2008 doi

  20. [28]

    Covering Codes

    Cohen G, Honkala I, Litsyn S, Lobstein A. Covering Codes . Elsevier, 1997. ISBN: 9780444825117

    1997

  21. [29]

    Covering problems for dichoto mized matchings

    Stanton R, Kalbfleisch J. Covering problems for dichoto mized matchings. Aequ. Math., 1968. 1:94–103. doi:10.1007/BF01817562

    1968 doi

  22. [30]

    New binary covering codes obtained by simulate d annealing

    Wille L. New binary covering codes obtained by simulate d annealing. IEEE Trans. Inf. Theory , 1996. 42(1):300–302

    1996

  23. [31]

    Unidirectional covering codes.IEEE Trans

    ¨Osterg˚ ard P , Seuranen E. Unidirectional covering codes.IEEE Trans. Inf. Theory , 2005. 52(1):336–340. doi:10.1109/TIT.2005.860449

    2005 doi

  24. [32]

    A Generalization of the Football Pool Pro blem

    V erstraten K. A Generalization of the Football Pool Pro blem. https://oeis.org/A238305/a238305.pdf, 2014

    2014

  25. [33]

    (Total) Domination in Prisms

    Azarija J, Henning M, Klavˇ zar S. (Total) Domination in Prisms. Electron. J. Comb. , 2017. 24(1):P19. doi:10.37236/6288

    2017 doi

  26. [34]

    A note on domination and total dom ination in prisms

    Goddard W , Henning MA. A note on domination and total dom ination in prisms. J. Comb. Optim., 2018. 35:14–20. doi:10.1007/s10878-017-0150-0

    2018 doi

  27. [35]

    Optimal lower bound for 2-identi fying codes in the hexagonal grid

    Junnila V , Laihonen T. Optimal lower bound for 2-identi fying codes in the hexagonal grid. Electron. J. Comb., 2012. 19(2):P38. doi:10.37236/2414

    2012 doi

  28. [36]

    Exact minimum density of codes ide ntifying vertices in the square grid

    Ben-Haim Y , Litsyn S. Exact minimum density of codes ide ntifying vertices in the square grid. SIAM J. Discrete Math., 2005. 19:69–82. doi:10.1137/S0895480104444089. 378 P . Herva et al. / Optimal Local Identifying and Local Locating-dominating C odes

    2005 doi

  29. [37]

    New bounds on the minimum density of an identifying code for the infinite hexagonal grid

    Cukierman A, Y u G. New bounds on the minimum density of an identifying code for the infinite hexagonal grid. Discret. Appl. Math., 2013. 161:2910–2924. doi:10.1016/j.dam.2013.06.002

    2013 doi

  30. [38]

    Bounds for codes identif ying vertices in the hexagonal grid

    Cohen G, Honkala I, Lobstein A. Bounds for codes identif ying vertices in the hexagonal grid. SIAM J. Discrete Math., 2000. 13:492–504. doi:10.1137/S089548019936099

    doi

  31. [39]

    Identifying codes with sm all radius in some infinite regular graphs

    Charon I, Hudry O, Lobstein A. Identifying codes with sm all radius in some infinite regular graphs. Electron. J. Comb., 2002. 9(1):R11. doi:10.37236/1628

    2002 doi

  32. [40]

    On codes identifying ver tices in the two-dimensional square lattice with diagonals

    Cohen G, Honkala I, Lobstein A. On codes identifying ver tices in the two-dimensional square lattice with diagonals. IEEE Trans. on Comput., 2001. 50:174–176. doi:10.1109/12.908992

    2001 doi

  33. [41]

    On locating-dominating sets in i nfinite grids

    Honkala I, Laihonen T. On locating-dominating sets in i nfinite grids. Eur . J. Comb., 2006. 27:218–227. doi:10.1016/j.ejc.2004.09.002

    2006 doi

  34. [42]

    An optimal locating-dominating set in the in finite triangular grid

    Honkala I. An optimal locating-dominating set in the in finite triangular grid. Discrete Math. , 2006. 306:2670–2681. doi:10.1016/j.disc.2006.04.028

    2006 doi

  35. [43]

    An introduction to the dischargin g method via graph coloring

    Cranston DW , West DB. An introduction to the dischargin g method via graph coloring. Discrete Mathe- matics, 2017. 340(4):766–793. doi:10.1016/j.disc.2016.11.022

    2017 doi

Pith tools

Reviewed May 24, 2026 · model on record in the stance chip above.