pith. sign in

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

Optimal local identifying and local locating-dominating codes

Pyry Herva , Tero Laihonen , Tuomo Lehtil\"a This is my paper

Pith reviewed 2026-05-24 10:06 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords local identifying codeslocal locating-dominating codeshypercubescovering codesgrid graphscode densityasymptotic boundsoptimal constructions
0
0 comments X

The pith

Local 1-identifying codes in the hypercube have asymptotically the same minimal density as covering codes.

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

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.

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.

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.

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.

Where Pith is reading between the lines

These are 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.

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.

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.

Figures

Figures reproduced from arXiv: 2302.13351 by Pyry Herva, Tero Laihonen, Tuomo Lehtil\"a.

Figure 1
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. 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. Figure 3: The darkened vertices form a (non-optimal) coveri [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
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] view at source ↗
Figure 5
Figure 5. Figure 5: Local location-domination in the square and hexag [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Local identifying codes in the square and hexagona [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Local identifying and locating-dominating codes [PITH_FULL_IMAGE:figures/full_fig_p019_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Constellations in the king grid. The edges have bee [PITH_FULL_IMAGE:figures/full_fig_p022_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Constellations in the king grid. The edges have bee [PITH_FULL_IMAGE:figures/full_fig_p024_9.png] view at source ↗
read the original 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.

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 / 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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 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.

axioms (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 no independent evidence
    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 no independent evidence
    purpose: A variant of locating-dominating codes with the same local identification requirement
    Newly introduced class whose minimum density is studied in grids.

pith-pipeline@v0.9.0 · 5704 in / 1338 out tokens · 28067 ms · 2026-05-24T10:06:37.473634+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

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

  9. [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

    work page doi:10.1016/j.amc.2019.124676 2020

  10. [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

    work page 2021

  11. [11]

    Lokaali identifiointi graafeissa (in Finnish)

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

    work page 2020

  12. [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

    work page

  13. [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

    work page doi:10.1016/0304-3975(87)90067-3 1987

  14. [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

    work page doi:10.1090/dimacs/056/07 1999

  15. [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

    work page 2002

  16. [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

    work page doi:10.1007/s40840-022-01459-x 2023

  17. [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. Springer, 2023 pp. 121–133. doi:10.1007/978-3-031-25211-2 9. P . Herva et al. / ...

    work page doi:10.1007/978-3-031-25211-2 2023

  18. [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

    work page 2002

  19. [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

    work page doi:10.37236/2417 2012

  20. [20]

    A Benchmark of PDF Information Extraction Tools Using a Multi-task and Multi- domain Evaluation Framework for Academic Documents,

    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

    work page doi:10.1007/978 2022

  21. [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

    work page doi:10.1016/j.tcs.2023.114061 2023

  22. [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

    work page doi:10.1016/j.ejc.2009.03.032 2010

  23. [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

    work page doi:10.46298/dmtcs.322 2004

  24. [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

    work page 2007

  25. [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

    work page doi:10.1007/s10623-021-00963-8 2022

  26. [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

    work page doi:10.1016/s0012-365x(01)00113-3 2001

  27. [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

    work page doi:10.1016/j.dam.2007.09.017 2008

  28. [28]

    Covering Codes

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

    work page 1997

  29. [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

    work page doi:10.1007/bf01817562 1968

  30. [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

    work page 1996

  31. [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

    work page doi:10.1109/tit.2005.860449 2005

  32. [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

    work page 2014

  33. [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

    work page doi:10.37236/6288 2017

  34. [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

    work page doi:10.1007/s10878-017-0150-0 2018

  35. [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

    work page doi:10.37236/2414 2012

  36. [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

    work page doi:10.1137/s0895480104444089 2005

  37. [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

    work page doi:10.1016/j.dam.2013.06.002 2013

  38. [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

    work page doi:10.1137/s089548019936099 2000

  39. [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

    work page doi:10.37236/1628 2002

  40. [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

    work page doi:10.1109/12.908992 2001

  41. [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

    work page doi:10.1016/j.ejc.2004.09.002 2006

  42. [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

    work page doi:10.1016/j.disc.2006.04.028 2006

  43. [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

    work page doi:10.1016/j.disc.2016.11.022 2017