Self-identifying codes in direct products of complete graphs with paths and cycles

Hao Qi; Jihong Liu; Zhangwei Shan

arxiv: 2512.22033 · v2 · submitted 2025-12-26 · 🧮 math.CO

Self-identifying codes in direct products of complete graphs with paths and cycles

Jihong Liu , Hao Qi , Zhangwei Shan This is my paper

Pith reviewed 2026-05-16 19:26 UTC · model grok-4.3

classification 🧮 math.CO

keywords self-identifying codesdirect productcomplete graphpathcycleidentifying codesdominating setsgraph theory

0 comments

The pith

Minimum self-identifying codes in K_m times paths or cycles have size linear in the length n with m-dependent coefficients.

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

The paper derives upper and lower bounds on the smallest self-identifying code in the direct product of a complete graph K_m with a path P_n or cycle C_n. These bounds are linear in n, with the leading coefficient depending only on m, and the bounds match asymptotically as n grows large. For paths with m and n at least 3 the resulting size is close to the size of an ordinary identifying code in the same graph. Readers care because self-identifying codes give a stricter unique-localization guarantee than standard identifying sets, which matters for sensor placement or fault detection in product networks.

Core claim

We obtain bounds on the minimum size of a self-identifying code in the direct products K_m×P_n and K_m×C_n that are linear in n with coefficients depending on m, and these bounds are asymptotically tight. In particular, for K_m×P_n with m,n≥3, our bounds closely approaches the size of an identifying code in the same graph, as determined by Shinde and Waphare.

What carries the argument

The intersection properties of closed neighborhoods in the direct product K_m × P_n (or C_n), which are used both to construct repeating patterns that dominate and separate vertices and to prove matching lower bounds via counting arguments on how many vertices each code vertex can uniquely cover.

If this is right

The minimal code size is Theta(n) for each fixed m as n tends to infinity.
For K_m × P_n with m,n≥3 the self-identifying code size is asymptotically the same as the identifying code size up to lower-order terms.
Explicit periodic constructions achieve the upper bounds for both the path and cycle cases.
The same linear-density approach works uniformly for all m≥2 and sufficiently large n.

Where Pith is reading between the lines

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

The same neighborhood-counting technique may yield linear bounds for direct products of K_m with other graphs that have bounded degree or regular structure.
The closeness to identifying-code size suggests that the extra self-identification constraint adds only a small constant-factor overhead in these products.
For applications such as network monitoring, the constructions give explicit sensor placements whose number grows only linearly with the length of the path or cycle dimension.

Load-bearing premise

The neighborhood intersections in the direct product must behave exactly as required by the self-identifying definition without extra overlaps that would prevent the linear separation for the given range of m and n.

What would settle it

An explicit construction, for some fixed m≥3 and large n, of a self-identifying code whose size is smaller than the paper's stated lower bound by more than a constant factor, or a proof that the minimal size must grow faster than linear in n.

Figures

Figures reproduced from arXiv: 2512.22033 by Hao Qi, Jihong Liu, Zhangwei Shan.

**Figure 1.** Figure 1: Illustration of the direct product structure and a self-identifying code. vertices belonging to a code S are marked as solid black circles. For clarity, edges are sometimes omitted in schematic drawings. Standard graph-theoretic terminology follows Bondy and Murty (2008); West (2001). We also use the interval notation [a, b] = {a, a + 1, . . . , b}. The following basic lemma imposes a necessary degree cond… view at source ↗

**Figure 2.** Figure 2: Visualization of the constructed self-identifying code S (black vertices) for Km × Pn when n is even. (a) n = 3k, k odd (b) n = 3k + 1, k odd (c) n = 3k + 2, k odd [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: Visualization of the constructed self-identifying code S (black vertices) for Km × Pn when n is odd. The upper bounds for the smaller cases 3 ≤ n ≤ 6 involve more specialized constructions and are therefore presented separately in Appendix 5. With the proof for n ≥ 7 now complete, Theorem 2.1 is fully established [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

**Figure 4.** Figure 4: Schematic of the constructed self-identifying code S (black vertices) for Km × Cn when k = ⌊n/3⌋ is even. A systematic verification confirms that the constructed set S satisfies all local criteria of Observation 4.1. The periodic nature of Cn ensures that the conditions hold for all vertices, including those that would be boundaries in the path case. Figures 4 and 5 provide schematic illustrations of the … view at source ↗

**Figure 5.** Figure 5: Schematic of the constructed self-identifying code S (black vertices) for Km × Cn when k = ⌊n/3⌋ is odd. 5 Concluding Remarks This paper determines the asymptotic density of self-identifying codes in the direct products Km × Pn and Km × Cn. We establish that for m ≥ 3, this density is exactly 1 3 as n → ∞. This result reveals a key theoretical insight: although a self-identifying code is a strictly stronge… view at source ↗

**Figure 6.** Figure 6: Optimal self-identifying codes (black vertices) for K3 × Pn with 3 ≤ n ≤ 6 [PITH_FULL_IMAGE:figures/full_fig_p013_6.png] view at source ↗

**Figure 7.** Figure 7: Optimal self-identifying codes for Km × Pn with m ≥ 4 and n ∈ {3, 4}. A.3 The Cases Km × P5 and Km × P6 for m ≥ 4 The optimal constructions for n = 5 and n = 6 exhibit a dependency on whether m is small (4 or 5) or large (≥ 6). Theorem A.3 For m ∈ {4, 5}, the minimum sizes are γ SID(Km × Pn) = ( 2m + 6, n = 5, 4m, n = 6. Proof: As before, the lower bounds are provided by Lemma 3.1 and Corollary 3.1. The up… view at source ↗

**Figure 8.** Figure 8: Optimal self-identifying codes for Km × Pn with m ∈ {4, 5} and n ∈ {5, 6}. For larger m, the optimal pattern changes, yielding a different formula. Theorem A.4 For all m ≥ 6, γ SID(Km × Pn) = ( 3m, n = 5, 3m + 6, n = 6. Proof: The lower bounds remain as before. The matching constructions, illustrated in [PITH_FULL_IMAGE:figures/full_fig_p015_8.png] view at source ↗

**Figure 9.** Figure 9: Optimal self-identifying codes for Km × Pn with m ≥ 6 and n ∈ {5, 6} [PITH_FULL_IMAGE:figures/full_fig_p015_9.png] view at source ↗

read the original abstract

Identifying codes were introduced by Karpovsky et al. as dominating sets $S\subseteq V(G)$ satisfying $N[u]\cap S \neq N[v]\cap S$ for any distinct vertices $u,v$. Later, Junnila et al. introduced the concept of \emph{self-identifying codes} (previously called $(1,\leq1)^+$-identifying codes in earlier work), a dominating set $S\subseteq V(G)$ such that $\bigcap_{c\in N[u]\cap S} N[c] = \{u\}$ for every vertex $u$. In this paper, we obtain bounds on the minimum size of a self-identifying code in the direct products $K_m\times P_n$ and $K_m\times C_n$ that are linear in $n$ with coefficients depending on $m$, and these bounds are asymptotically tight. In particular, for $K_m\times P_n$ with $m,n\ge3$, our bounds closely approaches the size of an identifying code in the same graph, as determined by Shinde and Waphare.

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.

Desk Editor's Note private letter to a colleague

The paper pins down linear bounds for the smallest self-identifying code in K_m × P_n and K_m × C_n that match asymptotically and sit close to the known identifying-code sizes.

read the letter

The main result is that Liu, Qi, and Shan give explicit linear upper and lower bounds on the minimum size of a self-identifying code in the direct products K_m × P_n and K_m × C_n, with the coefficient depending only on m, and they show these bounds are asymptotically tight as n grows. For the path case with m, n ≥ 3 the self-identifying size ends up close to the identifying-code size already determined by Shinde and Waphare. They achieve this by using the product structure to control neighborhood intersections and by supplying periodic constructions that satisfy the stricter self-identifying condition ∩ N[c] = {u} while keeping the size linear. The work is a direct, clean extension of the earlier identifying-code results to the self-identifying variant, and the absence of fitted parameters or circular definitions keeps the argument straightforward. The one soft spot worth checking is the uniformity of the intersection properties across all m and residue classes of n. The stress-test note correctly flags that extra horizontal neighbors in the K_m layers could create unintended common neighbors for some choices of S, which would force a strictly larger coefficient if the separation argument does not cover every case. If the full paper supplies the explicit constructions and verifies the equality for the chosen periodic sets, the tightness claim holds; otherwise the lower bound may need a modest correction. A reader who already knows the Shinde–Waphare paper will get the most out of this one and can check the new intersection arguments in a few pages. It is worth sending to peer review because the claims are concrete, the extension is natural, and the potential flaw is local rather than load-bearing.

Referee Report

2 major / 2 minor

Summary. The paper obtains linear-in-n bounds (with m-dependent coefficients) on the minimum size of self-identifying codes in the direct products K_m × P_n and K_m × C_n for m,n ≥ 3, proves these bounds are asymptotically tight, and shows that for K_m × P_n the self-identifying-code size closely approaches the identifying-code size previously determined by Shinde and Waphare.

Significance. If the constructions and separation arguments are correct, the results establish that the stricter self-identifying condition can be satisfied with only a small additive overhead relative to ordinary identifying codes in these product graphs. This supplies concrete, asymptotically optimal families and strengthens the link between the two notions of identification in graph products.

major comments (2)

[§4 (Constructions and lower bounds for K_m × P_n)] The lower-bound tightness argument for K_m × P_n rests on the claim that the periodic construction S satisfies ∩_{c ∈ N[u] ∩ S} N[c] = {u} for every vertex u. The direct-product neighborhood structure (horizontal neighbors at j±1 for all k ≠ i together with the two vertical neighbors at the same i) must be checked explicitly to ensure no unintended common neighbors appear for any residue class of the path coordinate j when m ≥ 3; this verification is load-bearing for the claimed coefficient.
[Abstract and §3–§5] The manuscript asserts that the obtained linear upper and lower bounds are asymptotically tight, yet the abstract and the provided text supply neither the explicit periodic construction nor the separation argument that would confirm the intersection property holds uniformly. Without these details the central claim cannot be verified.

minor comments (2)

[§2 (Preliminaries)] Notation for the direct product should be stated once at the beginning (e.g., whether × denotes the direct product with edges (u,v)∼(u′,v′) iff u∼u′ and v∼v′) to avoid ambiguity with Cartesian product.
[Introduction] The reference to Shinde and Waphare should include the exact statement of their identifying-code size for K_m × P_n so that the claimed proximity can be compared directly.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and for highlighting the need for explicit verification of the key claims. We will revise the manuscript to include the requested details on the periodic construction and the intersection-property checks, thereby making the asymptotic tightness fully verifiable while preserving the original results.

read point-by-point responses

Referee: [§4 (Constructions and lower bounds for K_m × P_n)] The lower-bound tightness argument for K_m × P_n rests on the claim that the periodic construction S satisfies ∩_{c ∈ N[u] ∩ S} N[c] = {u} for every vertex u. The direct-product neighborhood structure (horizontal neighbors at j±1 for all k ≠ i together with the two vertical neighbors at the same i) must be checked explicitly to ensure no unintended common neighbors appear for any residue class of the path coordinate j when m ≥ 3; this verification is load-bearing for the claimed coefficient.

Authors: We agree that an explicit verification of the intersection property is necessary given the neighborhood structure of the direct product. In the revised manuscript we will add a dedicated lemma (or subsection) that performs a case analysis over the possible residues of the path coordinate j modulo the period of S, confirming that for every u the only vertex whose closed neighborhood intersects S exactly in the same set as u is u itself. This will be done uniformly for m ≥ 3. revision: yes
Referee: [Abstract and §3–§5] The manuscript asserts that the obtained linear upper and lower bounds are asymptotically tight, yet the abstract and the provided text supply neither the explicit periodic construction nor the separation argument that would confirm the intersection property holds uniformly. Without these details the central claim cannot be verified.

Authors: We acknowledge that the current presentation does not display the periodic construction and the accompanying separation argument with sufficient prominence. In the revision we will (i) state the explicit periodic set S in §4, (ii) include the full intersection-property proof as a new lemma, and (iii) update the abstract to reference these elements so that the asymptotic tightness (both upper and lower bounds) can be verified directly from the text. revision: yes

Circularity Check

0 steps flagged

No circularity: bounds derived from explicit constructions and external prior result on identifying codes

full rationale

The paper derives linear upper and lower bounds on the minimum size of self-identifying codes in K_m×P_n and K_m×C_n directly from the neighborhood intersection properties of the direct product graph and explicit periodic constructions. The asymptotic tightness claim references the identifying-code size from Shinde and Waphare (distinct authors, no self-citation chain). No parameters are fitted to subsets of the target data, no self-definitional equations appear, and the separation arguments rest on the graph definition rather than on the claimed bound itself. The derivation is therefore self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the standard definitions of direct products, closed neighborhoods, and the self-identifying condition introduced by Junnila et al.; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)

standard math Direct product of graphs preserves the neighborhood intersection rules used in the self-identifying code definition.
Invoked implicitly when translating the code condition from the product graph back to the factors.

pith-pipeline@v0.9.0 · 5492 in / 1280 out tokens · 28781 ms · 2026-05-16T19:26:44.634968+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

doi: 10.1016/j.dam.2011.04.025. J. A. Bondy and U. S. R. Murty.Graph Theory. Springer, London,

work page doi:10.1016/j.dam.2011.04.025 2011
[2]

12 Jihong Liu et

doi: 10.1016/j.na.2006.12.004. 12 Jihong Liu et. al S. Gravier, A. Parreau, S. Rottey, L. Storme, and ´E. Vandomme. Identifying codes in vertex- transitive graphs and strongly regular graphs.Electronic Journal of Combinatorics, 22(4):P4.6,

work page doi:10.1016/j.na.2006.12.004 2006
[3]

doi: 10.1016/j.ipl.2006.11.007. I. Honkala, T. Laihonen, and S. Ranto. On codes identifying sets of vertices in hamming spaces.Designs, Codes and Cryptography, 24:193–204,

work page doi:10.1016/j.ipl.2006.11.007 2006
[4]

doi: 10.1023/A:1011256721935. I. Honkala, M. G. Karpovsky, and L. B. Levitin. On robust and dynamic identifying codes.IEEE Trans- actions on Information Theory, 52:599–612,

work page doi:10.1023/a:1011256721935
[5]

doi: 10.1109/TIT.2005.862097. O. Hudry and A. Lobstein. More results on the complexity of identifying problems in graphs.Theoretical Computer Science, 626:1–12,

work page doi:10.1109/tit.2005.862097 2005
[6]

doi: 10.1016/j.tcs.2016.01.021. D. C. Jean. Watching systems, identifying, locating-dominating and discriminating codes in graphs,

work page doi:10.1016/j.tcs.2016.01.021 2016
[7]

doi: 10.1016/j.aam.2019.101938. V . Junnila, T. Laihonen, and G. Paris. Location in circulant graphs. InRussian Finnish Symposium on Discrete Mathematics, pages 81–84,

work page doi:10.1016/j.aam.2019.101938 2019
[8]

doi: 10.1007/s12095-018-0316-3. M. G. Karpovsky, K. Chakrabarty, and L. B. Levitin. On a new class of codes for identifying vertices in graphs.IEEE Transactions on Information Theory, 44(2):599–611,

work page doi:10.1007/s12095-018-0316-3
[9]

On a new class of codes for identifying vertices in graphs

doi: 10.1109/18.661507. Matematikan ja Tilastotieteen Laitos. On lower bounds of various dominating codes for locating ver- tices in cubic graphs,

work page doi:10.1109/18.661507
[10]

doi: 10.1109/PGEC.1967. 264748. N. V . Shinde, S. A. Mane, and B. N. Waphare. Identifying codes in the direct product of a path and a complete graph.Discussiones Mathematicae Graph Theory, 43:463–486,

work page doi:10.1109/pgec.1967 1967
[11]

doi: https://doi.org/ 10.7151/dmgt.2380. P. J. Slater. Dominating and reference sets in a graph.Journal of Mathematical and Physical Sciences, 22:445–455,

work page doi:10.7151/dmgt.2380
[12]

S. J. Song, W. Zhang, and C. Xu. Locating and identifying codes in circulant graphs.Discrete Dynamics in Nature and Society, 2021:1–9,

work page 2021
[13]

On the Density of Self-identifying Codes inK m ×P n andK m ×C n 13 D

doi: 10.1155/2021/4056910. On the Density of Self-identifying Codes inK m ×P n andK m ×C n 13 D. B. West.Introduction to graph theory. Prentice Hall, Upper Saddle River, NJ, 2nd edition,

work page doi:10.1155/2021/4056910 2021
[14]

doi: 10.1002/(SICI)1097-0037(199708)30:1⟨73::AID-NET8⟩3.0.CO;2-I. Appendix A: Self-Identifying Codes inK m ×P n for Smalln This appendix complements the asymptotic results of Sections 3.1–3.2 by determining the exact values of γSID(Km ×P n)for small path lengths3≤n≤6. These precise formulas are obtained through a case analysis and explicit constructions. ...

work page doi:10.1002/(sici)1097-0037(199708)30:1

[1] [1]

doi: 10.1016/j.dam.2011.04.025. J. A. Bondy and U. S. R. Murty.Graph Theory. Springer, London,

work page doi:10.1016/j.dam.2011.04.025 2011

[2] [2]

12 Jihong Liu et

doi: 10.1016/j.na.2006.12.004. 12 Jihong Liu et. al S. Gravier, A. Parreau, S. Rottey, L. Storme, and ´E. Vandomme. Identifying codes in vertex- transitive graphs and strongly regular graphs.Electronic Journal of Combinatorics, 22(4):P4.6,

work page doi:10.1016/j.na.2006.12.004 2006

[3] [3]

doi: 10.1016/j.ipl.2006.11.007. I. Honkala, T. Laihonen, and S. Ranto. On codes identifying sets of vertices in hamming spaces.Designs, Codes and Cryptography, 24:193–204,

work page doi:10.1016/j.ipl.2006.11.007 2006

[4] [4]

doi: 10.1023/A:1011256721935. I. Honkala, M. G. Karpovsky, and L. B. Levitin. On robust and dynamic identifying codes.IEEE Trans- actions on Information Theory, 52:599–612,

work page doi:10.1023/a:1011256721935

[5] [5]

doi: 10.1109/TIT.2005.862097. O. Hudry and A. Lobstein. More results on the complexity of identifying problems in graphs.Theoretical Computer Science, 626:1–12,

work page doi:10.1109/tit.2005.862097 2005

[6] [6]

doi: 10.1016/j.tcs.2016.01.021. D. C. Jean. Watching systems, identifying, locating-dominating and discriminating codes in graphs,

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

[7] [7]

doi: 10.1016/j.aam.2019.101938. V . Junnila, T. Laihonen, and G. Paris. Location in circulant graphs. InRussian Finnish Symposium on Discrete Mathematics, pages 81–84,

work page doi:10.1016/j.aam.2019.101938 2019

[8] [8]

doi: 10.1007/s12095-018-0316-3. M. G. Karpovsky, K. Chakrabarty, and L. B. Levitin. On a new class of codes for identifying vertices in graphs.IEEE Transactions on Information Theory, 44(2):599–611,

work page doi:10.1007/s12095-018-0316-3

[9] [9]

On a new class of codes for identifying vertices in graphs

doi: 10.1109/18.661507. Matematikan ja Tilastotieteen Laitos. On lower bounds of various dominating codes for locating ver- tices in cubic graphs,

work page doi:10.1109/18.661507

[10] [10]

doi: 10.1109/PGEC.1967. 264748. N. V . Shinde, S. A. Mane, and B. N. Waphare. Identifying codes in the direct product of a path and a complete graph.Discussiones Mathematicae Graph Theory, 43:463–486,

work page doi:10.1109/pgec.1967 1967

[11] [11]

doi: https://doi.org/ 10.7151/dmgt.2380. P. J. Slater. Dominating and reference sets in a graph.Journal of Mathematical and Physical Sciences, 22:445–455,

work page doi:10.7151/dmgt.2380

[12] [12]

S. J. Song, W. Zhang, and C. Xu. Locating and identifying codes in circulant graphs.Discrete Dynamics in Nature and Society, 2021:1–9,

work page 2021

[13] [13]

On the Density of Self-identifying Codes inK m ×P n andK m ×C n 13 D

doi: 10.1155/2021/4056910. On the Density of Self-identifying Codes inK m ×P n andK m ×C n 13 D. B. West.Introduction to graph theory. Prentice Hall, Upper Saddle River, NJ, 2nd edition,

work page doi:10.1155/2021/4056910 2021

[14] [14]

doi: 10.1002/(SICI)1097-0037(199708)30:1⟨73::AID-NET8⟩3.0.CO;2-I. Appendix A: Self-Identifying Codes inK m ×P n for Smalln This appendix complements the asymptotic results of Sections 3.1–3.2 by determining the exact values of γSID(Km ×P n)for small path lengths3≤n≤6. These precise formulas are obtained through a case analysis and explicit constructions. ...

work page doi:10.1002/(sici)1097-0037(199708)30:1