Self-identifying codes in direct products of complete graphs with paths and cycles
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913103379169280 |
|---|---|
| author | Liu, Jihong Qi, Hao Shan, Zhangwei |
| author_facet | Liu, Jihong Qi, Hao Shan, Zhangwei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_22033 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Self-identifying codes in direct products of complete graphs with paths and cycles Liu, Jihong Qi, Hao Shan, Zhangwei Combinatorics 05C69, 05C76, 68R99 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. |
| title | Self-identifying codes in direct products of complete graphs with paths and cycles |
| topic | Combinatorics 05C69, 05C76, 68R99 |
| url | https://arxiv.org/abs/2512.22033 |