2025/12/26 by Jihong Liu, Liu, Jihong, Hao Qi +3
Computer Science · #05C69 #05C76 #68R99 #Advanced Graph Theory Research #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · doi:10.48550/arxiv.2512.22033
openalex publication_date 2025/12/26 · openalex created_date 2025/12/30 · openalex updated_date 2026/07/28
Identifying codes were introduced by Karpovsky et al. as dominating sets S⊆ V(G) satisfying N[u]∩ S ≠ N[v]∩ S for any distinct vertices u,v. Later, Junnila et al. introduced the concept of self-identifying codes (previously called (1,≤1)+-identifying codes in earlier work), a dominating set S⊆ V(G) such that \bigcapc∈ N[u]∩ 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 Km× Pn and Km× Cn that are linear in n with coefficients depending on m, and these bounds are asymptotically tight. In particular, for Km× Pn with m,n≥3, our bounds closely approaches the size of an identifying code in the same graph, as determined by Shinde and Waphare.