
























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。