pith. sign in

arxiv: 2402.08264 · v3 · submitted 2024-02-13 · 💻 cs.DM · math.CO

On Iiro Honkala's contributions to identifying codes

Olivier Hudry , Ville Junnila , Antoine Lobstein This is my paper

Pith reviewed 2026-05-24 04:23 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords identifying codesdominating setsgraph theoryHamming spacesinfinite gridscomputational complexitycombinatorics
0
0 comments X

The pith

Iiro Honkala contributed to identifying codes by examining their computational complexity, properties in Hamming spaces and grids, relations to other graph parameters, structural traits of admitting graphs, and counts of optimal codes.

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

This survey paper compiles Iiro Honkala's research on identifying codes, which are dominating vertex sets that give every pair of vertices distinct sets of dominating codewords. It organizes the contributions into six areas: the complexity of computing such codes, combinatorial questions in binary Hamming spaces, behavior on infinite grids, ties to ordinary graph parameters such as domination number, structural features of graphs that admit them, and the enumeration of minimum-size examples. A reader interested in location-identifying placements in networks or error-correcting structures would see how these threads fit together through one researcher's body of work.

Core claim

The paper presents Honkala's contributions to identifying codes across the complexity of computing them, combinatorics in binary Hamming spaces, infinite grids, relationships with usual graph parameters, structural properties of graphs admitting them, and the number of optimal identifying codes.

What carries the argument

Identifying code: a dominating set C such that the sets of neighbors in C are distinct for every pair of vertices.

If this is right

  • Complexity results establish that minimum identifying codes are hard to compute in general graphs.
  • Combinatorial bounds and constructions exist for Hamming spaces and infinite grids.
  • Links to domination and other parameters allow transfer of known techniques between problems.
  • Structural characterizations identify which graphs support identifying codes.
  • Enumeration results quantify how many distinct minimum identifying codes a graph can possess.

Where Pith is reading between the lines

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

  • The surveyed results may guide sensor placement in finite networks modeled on grids or Hamming graphs.
  • Extending the complexity classifications to additional graph families would build directly on the covered work.
  • Counts of optimal codes could inform redundancy analysis in identification systems.

Load-bearing premise

The six listed aspects form a representative selection of Honkala's main contributions without major omissions.

What would settle it

Discovery of a substantial body of Honkala's published work on identifying codes that falls outside the six areas covered by the survey.

Figures

Figures reproduced from arXiv: 2402.08264 by Antoine Lobstein, Olivier Hudry, Ville Junnila.

Figure 1
Figure 1. Figure 1: Different graphs and codes. Black vertices repres [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The subgraph induced by a clause Ci = xj ∨ xh ∨ xk for the transformation from 3-SAT to 1-IdC. such a code can be provided by all the vertices αi with 1 6 i 6 m, the vertices xj or xj according to the Boolean value taken by the variable associated with xj and xj for 1 6 j 6 |U|, and all the vertices bj and cj for 1 6 j 6 |U|). This construction is generalized in [16] to any integer r. The NP-completeness o… view at source ↗
Figure 3
Figure 3. Figure 3: Partial representations of the four grids: (a) the [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A periodic 5-IdC in the square grid GS , of density 2/25; codewords are in black [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A periodic 1-IdC in the square grid GS , of density 7/20; codewords are in black. For r > 2, Theorem 4.2 specifies bounds for ∂ Id r (GS). The lower bound for r = 2 comes from [59]; the general lower bound for r > 3 comes from [10]*; all the upper bounds come from [51]*. Theorem 4.2. (a) For r = 2, 6 35 ≈ 0.17143 6 ∂ Id 2 (GS) 6 5 29 ≈ 0.17241. (b) For r > 3, 3 8r+4 6 ∂ Id r (GS) 6 ( 2 5r : r even 2r 5r 2−… view at source ↗
Figure 6
Figure 6. Figure 6: displays a 1-IdC with minimum density 2/9 on the left and a 3-IdC with minimum density 1/12 on the right. In fact, for r > 2, the periodic pattern of the r-IdC is similar to the one displayed here for r = 3: a rectangle with two rows and 2r columns, with only one codeword, located in the bottom left corner; the patterns are concatenated horizontally and then the resulting strip is replicated vertically wit… view at source ↗
Figure 7
Figure 7. Figure 7: The case n = 15, r = 3 of Theorem 5.5, Case (b); this graph is 3-twin-free and has diame￾ter r + 1 = 4. Theorem 5.5. ([2]*) (a) For r > 1, fD(r, 2r + 1) = 2r. (b) For r > 1 and n > 2r + 2, fD(r, n) = r + 1. (c) For r > 1 and n > 2r + 1, FD(r, n) = n − 1. • Size α of a maximum independent set In any connected graph of order n which is not the complete graph, α lies between 2 and n − 1 (the star). Theorem 1.… view at source ↗
Figure 8
Figure 8. Figure 8: A 3-terminal graph. Theorem 5.10. ([12]*) For r > 3, P2r+1 is not the only r-terminal graph. For r > 6, there are infinitely many r-terminal graphs. Observe that the construction of Theorem 5.10 does not work for r = 2; the problem remains open: Open problem 1. Apart from P5, do 2-terminal graphs exist? Another open problem is the situation for r ∈ {3, 4, 5}: Open problem 2. For r ∈ {3, 4, 5}, is the numbe… view at source ↗
Figure 9
Figure 9. Figure 9: Optimal 2-IdCs for C7 and P6; codewords are in black. • The case r = 1 It is known from [34] that, if G and G \ S are 1-twin-free, then we have Id1(G) − Id1(G \ S) 6 |S|. In particular, for v ∈ V , Id1(G) − Id1(G \ {v}) 6 1; moreover, the two inequalities are tight. Thus, removing one vertex cannot imply a large decrease of Id1: at most 1. But removing a vertex may imply a large increase of Id1, as shown i… view at source ↗
Figure 10
Figure 10. Figure 10: A partial representation (for I = {2, 3, k−1}) of the graphs involved in the proof of Theorem 5.11; codewords are in black. M. Pelto provided a sharper result in [75] (with graphs which are not necessarily connected): Theorem 5.12. ([75]) Let n be the order of G, S a proper subset of V and v ∈ V . (a) If n > 2 |S|−1 , then Id1(G \ S) − Id1(G) 6 n − 2|S| −  n − |S| 2 |S|  ; the inequality is tight for n … view at source ↗
Figure 11
Figure 11. Figure 11: Illustration of Theorem 5.14 for r = 3: in both graphs, the black vertices form an optimal 3-IdC; Id3(G) − Id3(G \ {v}) = 13 − 8 = 5. 5.4. Removing an edge Let G be a graph and e an edge of G. The problem considered here is similar to the previous one, but with the deletion of an edge instead of a vertex: given an r-twin-free graph G = (V, E) and an edge e ∈ E, and assuming that the graph G \ {e} is r-twi… view at source ↗
Figure 12
Figure 12. Figure 12: The two non-isomorphic optimal SOCs of F 3 ; the three black vertices are the codewords. On the other hand, [PITH_FULL_IMAGE:figures/full_fig_p025_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: The four non-isomorphic optimal 1-IdCs of [PITH_FULL_IMAGE:figures/full_fig_p025_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: The graph G1; only some edges are represented between the vertices of the three copies of F 3 and the extra vertex at the bottom. In both cases, all the vertices, including the extra vertex, are covered and separated from the others. More precisely, we obtain optimal 1-IdCs of G1. Observe that G1 has 25 vertices with ν1(G1) = 56 × 56 × 56 + 3 × 32 × 56 × 56 = 476 672. Replicating G1 k times provides a (di… view at source ↗
Figure 15
Figure 15. Figure 15: The scheme of the graph Gq (q > 3). Finally, based on the graphs Gq, we obtain the following theorem: Theorem 6.1. ([41]*) For an infinite number of integers n, there exist connected graphs of order n admitting approximately 2 0.770n different optimal 1-IdCs. For r > 1, other constructions, based on trees admitting many optimal r-IdCs, are proposed, leading to the next theorem, where 1+log2 5 2 is approxi… view at source ↗
read the original abstract

A set $C$ of vertices in a graph $G=(V,E)$ is an identifying code if it is dominating and any two vertices of $V$ are dominated by distinct sets of codewords. This paper presents a survey of Iiro Honkala's contributions to the study of identifying codes with respect to several aspects: complexity of computing an identifying code, combinatorics in binary Hamming spaces, infinite grids, relationships between identifying codes and usual parameters in graphs, structural properties of graphs admitting identifying codes, and number of optimal identifying codes.

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

Summary. This paper is a survey of Iiro Honkala's contributions to identifying codes in graphs. It organizes the review around six aspects listed in the abstract: complexity of computing an identifying code, combinatorics in binary Hamming spaces, infinite grids, relationships between identifying codes and usual graph parameters, structural properties of graphs admitting identifying codes, and the number of optimal identifying codes. The central claim is a descriptive enumeration of these contributions rather than any new derivations or quantitative results.

Significance. If the enumeration is accurate and representative, the survey would consolidate literature on identifying codes and provide a useful reference point for researchers working on domination, coding theory, and graph parameters. The paper does not ship machine-checked proofs or new falsifiable predictions, but its value lies in bibliographic organization of an individual's body of work across the listed topics.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review, accurate summary of the manuscript's scope, and recommendation to accept. The referee correctly notes that the paper is a descriptive survey organizing Iiro Honkala's contributions across the six listed aspects without introducing new results.

Circularity Check

0 steps flagged

No circularity: survey enumerates external contributions without derivations

full rationale

The paper is a bibliographic survey whose sole claim is a descriptive enumeration of Honkala's prior results across six listed aspects. No equations, parameters, predictions, or uniqueness theorems are introduced or derived within the manuscript itself. All referenced results originate from Honkala's independent publications; the present authors' own prior work is not invoked as a load-bearing premise. Consequently no step reduces to self-definition, fitted inputs, or self-citation chains. The reader's weakest assumption concerns only bibliographic completeness, which lies outside the circularity criteria.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is a survey paper with no new mathematical derivations. No free parameters, axioms, or invented entities are introduced by the authors.

pith-pipeline@v0.9.0 · 5612 in / 1100 out tokens · 25110 ms · 2026-05-24T04:23:45.254490+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

62 extracted references · 62 canonical work pages · 3 internal anchors

  1. [1]

    Induced paths in twin-free graphs, Electron

    Auger D. Induced paths in twin-free graphs, Electron. J. Combin. 15(1) (2008), N17. doi:10.37236/892. [2]* Auger D, Charon I, Honkala I, Hudry O, and Lobstein A. Edg e number, minimum degree, maximum inde- pendent set, radius and diameter in twin-free graphs, Adv. Math. Commun. 3(1) (2009), 97–114. Erratum

    work page doi:10.37236/892 2008

  2. [2]

    doi:10.3934/amc.2009.3.97

    3(4):429–430. doi:10.3934/amc.2009.3.97

    work page doi:10.3934/amc.2009.3.97 2009

  3. [3]

    Complexity res ults for identifying codes in planar graphs, Int

    Auger D, Charon I, Hudry O, and Lobstein A. Complexity res ults for identifying codes in planar graphs, Int. Trans. Oper . Res.2010. 17(6):691–710. doi:10.1111/j.1475-3995.2009.00750.x

    work page doi:10.1111/j.1475-3995.2009.00750.x 2010

  4. [4]

    Exact minimum density of codes i dentifying vertices in the square grid, SIAM J

    Ben-Haim Y , and Litsyn S. Exact minimum density of codes i dentifying vertices in the square grid, SIAM J. Discrete Math. 2005. 19:69–82. doi:10.1137/S089548010444408

    work page doi:10.1137/s089548010444408 2005

  5. [5]

    Codes identifiants et codes localisateurs-dominateurs sur certains graphes, m´ emoire de stage de maˆ ıtrise, ENST, Paris, France 2001, 28 pages

    Bertrand N. Codes identifiants et codes localisateurs-dominateurs sur certains graphes, m´ emoire de stage de maˆ ıtrise, ENST, Paris, France 2001, 28 pages. [6]* Blass U, Honkala I, and Litsyn S. On the size of identifyi ng codes, Lecture Notes in Comput. Sci. 1999. 1719:142–147. doi:10.1007/3-540-46796-3 14. [7]* Blass U, Honkala I, and Litsyn S. On bina...

    work page doi:10.1007/3-540-46796-3 2001

  6. [6]

    New identifying c odes in the binary Hamming space

    Charon I, Cohen G, Hudry O, and Lobstein A. New identifyin g codes in the binary Hamming space, European J. Combin. 2010. 31:491–501. doi:10.1016/j.ejc.2009.03.032. [10]* Charon I, Honkala I, Hudry O and Lobstein A. General bou nds for identifying codes in some infinite regular graphs, Electron. J. Combin. 2001. 8(1):R39. [11]* Charon I, Honkala I, Hudry O...

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

  7. [7]

    Identifying codes wit h small radius in some infinite regular graphs, Electron

    Charon I, Hudry O, and Lobstein A. Identifying codes wit h small radius in some infinite regular graphs, Electron. J. Combin. 2002. 9(1): R11

    work page 2002

  8. [8]

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

    Charon I, Hudry O, and Lobstein A. Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard, Theoret. Comput. Sci. 2003. 290:2109–2120. doi:10.1016/S0304-3975(02)00536-4

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

  9. [9]

    Extremal cardinaliti es for identifying and locating-dominating codes, Discrete Math

    Charon I, Hudry O, and Lobstein A. Extremal cardinaliti es for identifying and locating-dominating codes, Discrete Math. 2007. 307:356–366. doi:10.1016/j.disc.2005.09.027. [18]* Cohen G, Gravier S, Honkala I, Lobstein A, Mollard M, Pa yan Ch, and Z´ emor G. Improved identifying codes for the grid, Electron. J. Combin. 1999. 6(1):R19. [19]* Cohen G, Honkal...

    work page doi:10.1016/j.disc.2005.09.027 2007

  10. [10]

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

    Cukierman A, and Y u G. New bounds on the minimum density o f an identifying code for the infinite hexagonal grid, Discrete 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

  11. [11]

    Codes identifiants , m´ emoire de DEA ROCO

    Daniel M. Codes identifiants , m´ emoire de DEA ROCO. Universit´ e Joseph Fourier, Grenobl e, France. 2003, 46 pages

    work page 2003

  12. [12]

    Constructions of r-identifying codes and (r, ≤ l)-identifying codes, Indian J

    Dhanalakshmi R, and Durairajan C. Constructions of r-identifying codes and (r, ≤ l)-identifying codes, Indian J. Pure Appl. Math. 2019. 50:531–547. doi:10.1007/s13226-019-0343-6

    work page doi:10.1007/s13226-019-0343-6 2019

  13. [13]

    On location-dominati on of set of vertices in cycles and paths, Congr

    Exoo G, Junnila V , and Laihonen T. On location-dominati on of set of vertices in cycles and paths, Congr . Numer .2010. 202:97–112

    work page 2010

  14. [14]

    Locating v ertices using codes, Congr

    Exoo G, Junnila V , and Laihonen T, and Ranto S. Locating v ertices using codes, Congr . Numer .2008. 191:143–159

    work page 2008

  15. [15]

    Upper boun ds for binary identifying codes, Adv

    Exoo G, Junnila V , and Laihonen T, and Ranto S. Upper boun ds for binary identifying codes, Adv. in Appl. Math. 2009. 42:277–289. doi:10.1016/j.aam.2008.06.004

    work page doi:10.1016/j.aam.2008.06.004 2009

  16. [16]

    Improved b ounds on identifying codes in binary Ham- ming spaces, European J

    Exoo G, Junnila V , and Laihonen T, and Ranto R. Improved b ounds on identifying codes in binary Ham- ming spaces, European J. Combin. 2010. 31:813–827. doi:10.1016/j.ejc.2009.09.002

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

  17. [17]

    Improved upper bounds on binary identifying codes, IEEE Trans

    Exoo G, Laihonen T, and Ranto S. Improved upper bounds on binary identifying codes, IEEE Trans. Inform. Theory. 2007. 53:4255–4260. doi:10.1109/TIT.2007.907434

    work page doi:10.1109/tit.2007.907434 2007

  18. [18]

    New bounds on binary identif ying codes

    Exoo G, Laihonen T, and Ranto S. New bounds on binary iden tifying codes, Discrete Appl. Math. 2008. 156:2250–2263. doi:10.1016/j.dam.2007.09.017

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

  19. [19]

    Algorithmic and combinatorial aspects of identifying code s in graphs , PhD thesis, Universit´ e Bordeaux 1, France 2012

    Foucaud F. Algorithmic and combinatorial aspects of identifying code s in graphs , PhD thesis, Universit´ e Bordeaux 1, France 2012

    work page 2012

  20. [20]

    Decision and approximation complexity for i dentifying codes and locating-dominating sets in restricted graph classes

    Foucaud F. Decision and approximation complexity for i dentifying codes and locating-dominating sets in restricted graph classes. J. Discrete Alg. 2015. 31:48–68. doi:10.1016/j.jda.2014.08.004

    work page doi:10.1016/j.jda.2014.08.004 2015

  21. [21]

    Extremal graphs forthe identifying code problem, European J

    Foucaud F, Guerrini E, Kov ˇ se M, Naserasr R, Parreau A, and V alicov P . Extremal graphs forthe identifying code problem, European J. Combin. 2011. 32:628-638. doi:10.1016/j.ejc.2011.01.002

    work page doi:10.1016/j.ejc.2011.01.002 2011

  22. [22]

    Identifying path covers in graphs, J

    Foucaud F, and Kov ˇ se M. Identifying path covers in graphs, J. Discrete Alg. 2013. 23:21–34. doi:10.1016/j.jda.2013.07.006

    work page doi:10.1016/j.jda.2013.07.006 2013

  23. [23]

    An improved lower b ound for (1, ⩽ 2)-identifying codes in the king grid, Adv

    Foucaud F, Laihonen T, and Parreau A. An improved lower b ound for (1, ⩽ 2)-identifying codes in the king grid, Adv. Math. Commun. 2014. 8:35–52. doi:10.3934/amc.2014.8.35

    work page doi:10.3934/amc.2014.8.35 2014

  24. [24]

    Construction of codes identify ing sets of vertices, Electron

    Gravier S, and Moncel J. Construction of codes identify ing sets of vertices, Electron. J. Combin. 2005. 12(1):R13. doi:10.37236/1910

    work page doi:10.37236/1910 2005

  25. [25]

    On graphs having a V \ {x} set as an identifying code, Discrete Math

    Gravier S, and Moncel J. On graphs having a V \ {x} set as an identifying code, Discrete Math. 2007. 307:432–434. doi:10.1016/j.disc.2005.09.035. 194 O. Hudry et all. / On Iiro Honkala’s Contributions to Identifying Codes [39]* Honkala I. On the identifying radius of codes, Proceedings of the Seventh Nordic Combinatorial Confer- ence, Turku, TUCS Gen. Pub...

    work page doi:10.1016/j.disc.2005.09.035 2007

  26. [26]

    doi:10.1137/S009753970343311

    33:304–312. doi:10.1137/S009753970343311. [45]* Honkala I, and Laihonen T. On identifying codes that ar e robust against edge changes, Inform. and Com- put. 2007. 205:1078–1095. doi:10.1016/j.ic.2007.01.003. [46]* Honkala I, and Laihonen T. On a new class of identifying codes in graphs, Inform. Process. Lett. 2007. 102:92–98. doi:10.1016/j.ipl.2006.11.007...

    work page doi:10.1137/s009753970343311 2007

  27. [27]

    More results on the complexity o f identifying problems in graphs, Theor

    Hudry O, and Lobstein A. More results on the complexity o f identifying problems in graphs, Theor . Com- put. Sci. 2016. 626:1–12. doi:10.1016/j.tcs.2016.01.021

    work page doi:10.1016/j.tcs.2016.01.021 2016

  28. [28]

    Unique (optimal) solutions: co mplexity results for identifying and locating- dominating codes, Theor

    Hudry O, and Lobstein A. Unique (optimal) solutions: co mplexity results for identifying and locating- dominating codes, Theor . Comput. Sci.2019. 767:83–102. doi:10.1016/j.tcs.2018.09.034

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

  29. [29]

    On the size of identifying code s in binary hypercubes, J

    Janson S, and Laihonen T. On the size of identifying code s in binary hypercubes, J. Combin. Theory , Ser. A 2009. 116:1087–1096. doi:10.1016/j.jcta.2009.02.004. O. Hudry et all. / On Iiro Honkala’s Contributions to Identifying Codes 195

    work page doi:10.1016/j.jcta.2009.02.004 2009

  30. [30]

    Watching systems, identifying, locating-domi nating and discriminating codes in graphs, https://dragazo.github.io/bibdom/main.pdf

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

    work page

  31. [31]

    New lower bound for 2-identifying code in the square grid

    Junnila V . New lower bound for 2-identifying code in the square grid, Discrete Appl. Math. 2013. 161:2042–2051. doi:10.1016/j.dam.2013.02.032

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

  32. [32]

    Identification in Z2 using Euclidean balls, Discrete Appl

    Junnila V , and Laihonen T. Identification in Z2 using Euclidean balls, Discrete Appl. Math. 2011. 159:335–

    work page 2011

  33. [33]

    doi:10.1016/j.dam.2010.12.008

    work page doi:10.1016/j.dam.2010.12.008 2010

  34. [34]

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

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

    work page doi:10.37236/2414 2012

  35. [35]

    On a new cla ss of codes for identifying vertices in graphs, IEEE Trans

    Karpovsky MG, Chakrabarty K, and Levitin LB. On a new cla ss of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory 1998. 44:599–611

    work page 1998

  36. [36]

    Sequences of optimal identifying codes, IEEE Trans

    Laihonen T. Sequences of optimal identifying codes, IEEE Trans. Inform. Theory 2002. 48:774–776. doi:10.1109/18.986043

    work page doi:10.1109/18.986043 2002

  37. [37]

    Optimal codes for strong identification, European J

    Laihonen T. Optimal codes for strong identification, European J. Combin. 2002. 23:307–313. doi:10.1006/eujc.2002.0571

    work page doi:10.1006/eujc.2002.0571 2002

  38. [38]

    On optimal edge-robust and vertex-robust (1, ≤ ℓ)-identifying codes, SIAM J

    Laihonen T. On optimal edge-robust and vertex-robust (1, ≤ ℓ)-identifying codes, SIAM J. Discrete Math

    work page

  39. [39]

    doi:10.1137/S0895480104440754

    18(4):825–834. doi:10.1137/S0895480104440754

    work page doi:10.1137/s0895480104440754

  40. [40]

    Optimal t-edge-robust r-identifying codes in the king lattice, Graphs Combin

    Laihonen T. Optimal t-edge-robust r-identifying codes in the king lattice, Graphs Combin. 2006. 22:487–

    work page 2006

  41. [41]

    doi:10.1007/s00373-006-0682-z

    work page doi:10.1007/s00373-006-0682-z

  42. [42]

    On edge-robust (1, ≤ ℓ)-identifying codes in binary Hamming spaces, Int

    Laihonen T. On edge-robust (1, ≤ ℓ)-identifying codes in binary Hamming spaces, Int. J. Pure Appl. Math

    work page

  43. [43]

    doi:10.48550/arXiv.cs/0703066

    36:87–102. doi:10.48550/arXiv.cs/0703066

    work page doi:10.48550/arxiv.cs/0703066

  44. [44]

    Codes identifying sets of verti ces, in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Melbourne, 2001) , Lecture Notes in Comput

    Laihonen T, and Ranto S. Codes identifying sets of verti ces, in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Melbourne, 2001) , Lecture Notes in Comput. Sci. 2001. (2227):82–91. doi:10.1007/3-540-45624-4 9

    work page doi:10.1007/3-540-45624-4 2001

  45. [45]

    Families of optimal codes for st rong identification, Discrete Appl

    Laihonen T, and Ranto S. Families of optimal codes for st rong identification, Discrete Appl. Math. 2002. 121(1-3):203–213. doi:10.1016/S0166-218X(01)00248-7

    work page doi:10.1016/s0166-218x(01)00248-7 2002

  46. [46]

    Locating-domination and identification, in T

    Lobstein A, Hudry O, and Charon I. Locating-domination and identification, in T. Hayes, S. Hedetniemi, M. Henning (eds), T opics in Domination in Graphs , Springer 2020. pp. 251–299. https://hal.science/hal-02916929

    work page 2020

  47. [47]

    Lower bounds for identifying co des in some infinite grids, Electron

    Martin R, and Stanton B. Lower bounds for identifying co des in some infinite grids, Electron. J. Combin

    work page

  48. [48]

    Lower bounds for identifying codes in some infinite grids

    17(1):R122. doi:10.48550/arXiv.1004.3281

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1004.3281

  49. [49]

    Monotonicity of the minimum cardinality of an identifying code in the hypercube, Discrete Appl

    Moncel J. Monotonicity of the minimum cardinality of an identifying code in the hypercube, Discrete Appl. Math. 2006. 154:898–899. doi:10.1016/j.dam.2005.05.030

    work page doi:10.1016/j.dam.2005.05.030 2006

  50. [50]

    New bounds for (r, ⩽ 2)-identifying codes in the infinite king grid, Cryptogr

    Pelto M. New bounds for (r, ⩽ 2)-identifying codes in the infinite king grid, Cryptogr . Commun.2010. 2:41–47. doi:10.1007/s12095-009-0015-1

    work page doi:10.1007/s12095-009-0015-1 2010

  51. [51]

    On identifying and locating-dominating codes in the infinite king grid, PhD thesis, University of Turku, Finland, 2012

    Pelto M. On identifying and locating-dominating codes in the infinite king grid, PhD thesis, University of Turku, Finland, 2012

    work page 2012

  52. [52]

    Maximum difference about the size of optimal id entifying codes in graphs differing by one vertex, Discrete Math

    Pelto M. Maximum difference about the size of optimal id entifying codes in graphs differing by one vertex, Discrete Math. Theor . Comput. Sci. 2015. 17(1):339–356. doi:10.46298/dmtcs.2107

    work page doi:10.46298/dmtcs.2107 2015

  53. [53]

    On location-domination numbers for certain classes of graphs, Congr

    Rall DF, and Slater PJ. On location-domination numbers for certain classes of graphs, Congr . Numer .1984. 45:97-106. 196 O. Hudry et all. / On Iiro Honkala’s Contributions to Identifying Codes [77]* Ranto S, Honkala I, and Laihonen T. Two families of optimal identifying codes in binary Hamming spaces, IEEE Trans. Inform. Theory 2002. 48:1200–1203

    work page 1984

  54. [54]

    Computational complexity issues in operative diagnosis of graph-based systems, IEEE Trans

    Rao NSV . Computational complexity issues in operative diagnosis of graph-based systems, IEEE Trans. Comput. 1993. 42:447–457. doi:10.1109/12.214691

    work page doi:10.1109/12.214691 1993

  55. [55]

    Robust location detection in emergency sensor networks, Proceedings of INFOCOM 2003, San Francisco, USA (2003):1044–1053

    Ray S, Ungrangsi R, Pellegrini F De, Trachtenberg A, and Starobinski D. Robust location detection in emergency sensor networks, Proceedings of INFOCOM 2003, San Francisco, USA (2003):1044–1053. doi:10.1109/INFCOM.2003.1208941

    work page doi:10.1109/infcom.2003.1208941 2003

  56. [56]

    On the identification of vertices using cyc les, Electron

    Rosendahl P . On the identification of vertices using cyc les, Electron. J. Combin. 2003. 10(1):R7. doi:10.37236/1700

    work page doi:10.37236/1700 2003

  57. [57]

    Finding codes on infinite grids automatically

    Salo V , and T¨ orm¨ a I. Finding codes on infinite grids automatically, to appear in Fund. Inform. 2024. (see also arXiv:2303.00557)

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  58. [58]

    Open neighborhood locating-domi nating sets, Australas

    Seo SJ, and Slater PJ. Open neighborhood locating-domi nating sets, Australas. J. Combin. 2010. 46:109–

    work page 2010

  59. [59]

    Domination and location in graphs, Research Report No

    Slater PJ. Domination and location in graphs, Research Report No. 93, National University of Singapore 1983

    work page 1983

  60. [60]

    Improved bounds for r-identifying codes of the hex grid, SIAM J

    Stanton B. Improved bounds for r-identifying codes of the hex grid, SIAM J. Discrete Math. 2011. 25:159–

    work page 2011

  61. [61]

    doi:10.1137/100791610

    work page doi:10.1137/100791610

  62. [62]

    Automated Discharging Arguments for Density Problems in Grids

    Stolee D. Automated Discharging Arguments for Density Problems in Grids, arXiv:1409.5922, ID:15143804

    work page internal anchor Pith review Pith/arXiv arXiv