路与圈笛卡尔积的自标识码

Self-Identifying Codes in Cartesian Products of Paths and Cycles

摘要: 令$G=\left(V,E\right)$ 为图，$V$ 为顶点集合，$E$ 为边集合。若子集$C\subseteq V\left(G\right)$ 满足：对任意$u\in V\left(G\right)$ ，$N\left[u\right]\cap C\ne \varnothing$ 且${\displaystyle {\cap }_{c\in N\left[u\right]\cap C}N\left[c\right]}=\left\{u\right\}$ ，则$C$ 称为$G$ 的自识别码。本文通过分而治之法和构造法，给出网格图($P_n\square P_m$ )、柱面网格图($P_n\square C_m$ )和环面图($C_n\square C_m$ )的自标识码数界的刻画，其中$\square$ 表示图的笛卡尔积。这些图类在传感器网络故障诊断中有重要应用。

Abstract: Let $G=\left(V,E\right)$ be a graph, where $V$ is the vertex set and $E$ is the edge set. A subset $C\subseteq V\left(G\right)$ is called a self-identifying code of $G$ if for every vertex $u\in V\left(G\right)$ , $N\left[u\right]\cap C\ne \varnothing$ , and ${\displaystyle {\cap }_{c\in N\left[u\right]\cap C}N\left[c\right]}=\left\{u\right\}$ . This paper uses divide-and-conquer methods and constructive approaches to characterize the bounds on the size of self-identifying codes in grid graphs ($P_n\square P_m$ ), cylindrical grid graphs ($P_n\square C_m$ ), and torus graphs ($C_n\square C_m$ ), where $\square$ denotes the cartesian product of graphs. These graph classes have important applications in fault diagnosis of sensor networks.