一些环的Nil-Clean图的导出子图中的完备码

Perfect Codes in Induced Subgraphs of Nil-Clean Graphs for Some Rings

摘要: 设$R$ 是一个环。如果一个元素$r\in R$ 可以分解成$R$ 中的一个幂等元与一个幂零元的和，那么就称$r$ 为$R$ 中的一个nil-clean元。$R$ 的nil-clean图记为$G_{NC}\left(R\right)$ ，其点集为$R$ ，两个不同的点$x$ 和$y$ 是邻接的当且仅当$x+y$ 是$R$ 中的一个nil-clean元。设$G$ 是一个有限无向简单图，其点集为$V\left(G\right)$ 。设$C$ 是$V\left(G\right)$ 的一个非空子集。如果当$c_i$ 取遍$C$ 中所有元素时，$c_i$ 的半径为1的闭邻域$S_1\left(c_i\right)$ 构成$V\left(G\right)$ 的一个划分，则称$C$ 为图$G$ 中的一个完备码。本文通过分析一些环的nil-clean图的导出子图的结构来确定这些图中完备码的大小，其中导出子图的点集为环的单位集。

Abstract: Let $R$ be a ring. If an element $r\in R$ can be decomposed into the sum of an idempotent element and a nilpotent element in $R$ , then $r$ is called a nil-clean element in $R$ . The nil-clean graph of $R$ is denoted as $G_{NC}\left(R\right)$ , whose point set is $R$ , and two different points $x$ and $y$ are adjacent if and only if $x+y$ is a nil-clean element of $R$ . Let $G$ be a finite undirected simple graph with vertex set $V\left(G\right)$ . Let $C$ be a non-empty subset of $V\left(G\right)$ . When $c_i$ runs through $C$ , if $S_1\left(c_i\right)$ form a partition of $V\left(G\right)$ , where $S_1\left(c_i\right)$ is the closed neighbourhood of $c_i$ with radius 1, then $C$ is called a perfect code in $G$ . In this paper, we determine the sizes of the perfect codes in the induced subgraphs of the nil-clean graphs of some rings by analyzing the structure of these graphs, where the vertex sets of the induced subgraphs are the unit sets of the rings.

1. 引言

完备码这一概念最初来源于编码理论，在信息传输中，为了纠正传输错误，需要设计纠错码，而完备码是“纠错能力最优”的码。在1973年，Biggs首次将完备码从经典码论推广到图论的范畴，且给出了距离传递图中完备码存在的判别准则[1]。这也开始了后续对凯莱图、交换图、双凯莱图等各类特殊图的完备码的研究。近年来，对代数结构上图的完备码的研究变得越来越热门。例如，Mudaber等人研究了一些环上不同图的完备码，2021年，他们确定了以环${\mathbb{Z}}_n$ 的幂等元集为点集的${\mathbb{Z}}_n$ 的单位图的导出子图中的完备码[2]；2022年，他们确定了阶为$2^n\left(n\ge 1\right)$ 的Boolean环的单位图的生成子图的完备码，刻画了单位图存在1阶和2阶完备码的交换环以及一些单位图及其补图不存在完备码的交换环，还研究了以环的单位集为点集的一些交换环的导出子图的完备码[3]-[5]；2024年，他们确定了一些交换环上单位积图的不同阶的完备码[6]。Ma等学者解决了对称群和交错群上交换图的完备码问题[7]。Huo等学者给出了一些有限非交换群上交换图的完备码[8]。

设$G$ 是一个有限无向简单图，其点集为$V\left(G\right)$ ，称$V\left(G\right)$ 的一个非空子集$C$ 为一个码。如果码$C$ 满足：当$c_i$ 取遍$C$ 中所有元素时，$c_i$ 的半径为1的闭邻域$S_1\left(c_i\right)$ 构成$V\left(G\right)$ 的一个划分，那么就称$C$ 为图$G$ 的一个完备码[1]。换句话说，如果对所有$c_i,c_j\in C$ ，满足$S\left(c_i\right)\cap S_1\left(c_j\right)=\varnothing$ 且$\cup S_1\left(c_i\right)=V\left(G\right)$ ，则码$C$ 就是$G$ 的一个完备码[9]。如果$C$ 中有$m$ 个元素，那么称$C$ 为$m$ 阶完备码，记为$\left|C\right|=m$ 。设$R$ 是一个环，对于环$R$ 中的一个元素$r$ ，如果存在元素$a\in Id\left(R\right)$ 和$b\in Nil\left(R\right)$ ，使得$r=a+b$ ，那么称元素$r$ 为环$R$ 中的一个nil-clean元，其中$Id\left(R\right)$ 为环$R$ 的幂等元集，$Nil\left(R\right)$ 为环$R$ 的幂零元集，把环$R$ 中所有nil-clean元构成的集合记为$NC\left(R\right)$ 。环$R$ 的nil-clean图是以$R$ 中所有元素为点集，两个不同点$x$ 和$y$ 是邻接的当且仅当$x+y\in NC\left(R\right)$ 。

根据单位图、零因子图等代数图的导出子图的研究，也让我们自然而然地开始研究nil-clean图的导出子图。环的单位集是环的核心代数结构，它直接决定环的整体性质。研究以环的单位集为点集的nil-clean图的导出子图，一方面可以简化nil-clean图的复杂度，另一方面可以反映出nil-clean图的整体结构，此外，还可以由导出子图的某种性质推断出原图的局部性质。本文根据不同的$n$ 值将模$n$ 剩余类环${\mathbb{Z}}_n$ 分类，确定这些环的nil-clean图的导出子图中完备码的大小。

2. 预备知识

注记2.1 (1) 记${\Gamma }_{NC}\left(R\right)$ 为环$R$ 的nil-clean图的导出子图，其点集为$R$ 的单位集$U\left(R\right)$ ；

1) 记$\lceil x\rceil$ 表示不小于$x$ 的最小整数；

2) 设$V\left(G\right)$ 是图$G$ 的点集，$x$ 是$V\left(G\right)$ 中的一点，则$V\left(G\right)\setminus \left\{x\right\}$ 表示从$V\left(G\right)$ 中去掉点$x$ 所得到的集合。

定义2.2 [10]设$R$ 是一个环。对于$R$ 中的一个元素$a$ ，如果存在一个幂等元$e\in R$ 和一个幂零元$b\in R$ ，使得$a=e+b$ ，那么就称元素$a$ 是$R$ 中的一个nil-clean元。如果$R$ 中的每个元素都是nil-clean元，那么称环$R$ 为nil-clean环。

定义2.3 [11]设$R$ 是一个环。$R$ 的nil-clean图记为$G_{NC}\left(R\right)$ ，其点集为$R$ ，两个不同点$x$ 和$y$ 是邻接的当且仅当$x+y$ 是$R$ 中的一个nil-clean元。

定义2.4 [12]设$G$ 和$H$ 是两个图，如果点集$V\left(H\right)\subseteq V\left(G\right)$ 且边集$E\left(H\right)\subseteq E\left(G\right)$ ，那么称$H$ 是$G$ 的一个子图，进一步地，若$E\left(H\right)=\left\{\left(x,y\right)\mid x,y\in V\left(H\right),\left(x,y\right)\in E\left(G\right)\right\}$ ，则称$H$ 是$G$ 的一个导出子图。

引理2.5 [11]设$p$ 是一个素数，则环${\mathbb{Z}}_p$ 的nil-clean图是一个有$p$ 个点的路径图$P_p$ 。

证明：当$p$ 是一个素数时，因为$Id\left({\mathbb{Z}}_p\right)=\left\{\overline{0},\overline{1}\right\}$ 且$Nil\left({\mathbb{Z}}_p\right)=\left\{\overline{0}\right\}$ ，所以$NC\left({\mathbb{Z}}_p\right)=\left\{\overline{0},\overline{1}\right\}$ 。${\mathbb{Z}}_p$ 的nil-clean图$G_{NC}\left({\mathbb{Z}}_p\right)$ 如图1：

Figure 1. The nil-clean graph of ${\mathbb{Z}}_p$

图1. ${\mathbb{Z}}_p$ 的nil-clean图

事实上，因为$\overline{0}+\overline{0}=\overline{0}\in NC\left({\mathbb{Z}}_p\right)$ ，$\overline{0}+\overline{1}=\overline{1}\in NC\left({\mathbb{Z}}_p\right)$ ，$\overline{\frac{p+1}{2}}+\overline{\frac{p+1}{2}}=\overline{1}\in NC\left({\mathbb{Z}}_p\right)$ ，$\overline{\frac{p+1}{2}}+\overline{\frac{p-1}{2}}=\overline{0}\in NC\left({\mathbb{Z}}_p\right)$ ，但本文只考虑简单图，则图中不含自环边，所以在图$G_{NC}\left({\mathbb{Z}}_p\right)$ 中，点$\overline{0}$ 只与$\overline{1}$ 邻接，点$\overline{\frac{p+1}{2}}$ 只与$\overline{\frac{p-1}{2}}$ 邻接，所以$\overline{0}$ 和$\overline{\frac{p+1}{2}}$ 的度都是1。而对任意一点$\overline{v}\in V\left(G_{NC}\left({\mathbb{Z}}_p\right)\right)\setminus \left\{\overline{0},\overline{\frac{p+1}{2}}\right\}$ ，因为$\overline{v}+\overline{0-v}=\overline{0}\in NC\left({\mathbb{Z}}_p\right)$ 且$\overline{v}+\overline{1-v}=\overline{1}\in NC\left({\mathbb{Z}}_p\right)$ ，所以$\overline{v}$ 只与$\overline{0-v}$ 和$\overline{1-v}$ 邻接，则$\overline{v}$ 的度为2。

3. 主要结果与证明

定理3.1 设${\Gamma }_{NC}\left({\mathbb{Z}}_p\right)$ 是环${\mathbb{Z}}_p$ 的nil-clean图的导出子图，其中$p$ 是一个素数，且$C$ 为该图的完备码，

则$\left|C\right|=\lceil \frac{p-1}{3}\rceil$ 。

证明：由引理2.5知，当$p$ 是一个素数时，$G_{NC}\left({\mathbb{Z}}_p\right)$ 是一个有$p$ 个点的路径图。而${\mathbb{Z}}_p$ 中所有的非零元都是单位，因此，${\Gamma }_{NC}\left({\mathbb{Z}}_p\right)$ 是一个有$p-1$ 个点的路径图。对${\Gamma }_{NC}\left({\mathbb{Z}}_p\right)$ 中的点进行重新标号后得到图2：

Figure 2. The relabeled induced subgraph of the nil-clean graph of ${\mathbb{Z}}_p$

图2. 重新标号后的${\mathbb{Z}}_p$ 的nil-clean图的导出子图

观察图2可知，$S_1\left(1\right)=\left\{1,2\right\}$ ，$S_1\left(p-1\right)=\left\{p-1,p-2\right\}$ ，$S_1\left(x\right)=\left\{x,x-1,x+1\right\}$ ，其中$x=2,3,\dots ,p-2$ 。

当$3\mid p-1$ 时，从第一个点开始，将三个点分成一组，只需把每组中间的点取为$C$ 中元素，即

$C=\left\{2,5,8,\cdots ,p-2\right\}$ 。因此，$\left|C\right|=\frac{p-1}{3}=\lceil \frac{p-1}{3}\rceil$ 。

当$3\nmid p-1$ 时，如果$3\mid p$ ，即$p=3$ ，则$C=\left\{1\right\}$ 或$C=\left\{2\right\}$ ，此时，$\left|C\right|=1=\lceil \frac{p-1}{3}\rceil$ ；如果$3\mid p-2$ ，观察图2可知，$C=\left\{1,4,7,\cdots ,p-1\right\}$ ，此时$\left|C\right|=\frac{p-2}{3}+1=\lceil \frac{p-1}{3}\rceil$ 。

例3.2 设${\Gamma }_{NC}\left(R\right)$ 为环$R$ 的nil-clean图的导出子图，$C$ 是它的完备码。

设$R={\mathbb{Z}}_7$ ，则$V\left({\Gamma }_{NC}\left({\mathbb{Z}}_7\right)\right)=U\left({\mathbb{Z}}_7\right)=\left\{\overline{1},\overline{2},\overline{3},\overline{4},\overline{5},\overline{6}\right\}$ ，易知$NC\left({\mathbb{Z}}_7\right)=\left\{\overline{0},\overline{1}\right\}$ ，所以${\mathbb{Z}}_7$ 的nil-clean图的导出子图如图3：

Figure 3. The induced subgraph of the nil-clean graph of ${\mathbb{Z}}_7$

图3. ${\mathbb{Z}}_7$ 的nil-clean图的导出子图

因为$3\mid \left(7-1\right)$ ，所以由定理3.1，$\left|C\right|=\lceil \frac{7-1}{3}\rceil =2$ ，观察图3可知，$C=\left\{\overline{3},\overline{6}\right\}$ 是${\Gamma }_{NC}\left({\mathbb{Z}}_7\right)$ 的一个完备码。

设$R={\mathbb{Z}}_{11}$ ，因为$V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{11}\right)\right)=U\left({\mathbb{Z}}_{11}\right)=\left\{\overline{1},\overline{2},\overline{3},\overline{4},\overline{5},\overline{6},\overline{7},\overline{8},\overline{9},\overline{10}\right\}$ 且$NC\left({\mathbb{Z}}_{11}\right)=\left\{\overline{0},\overline{1}\right\}$ ，所以${\mathbb{Z}}_{11}$ 的nil-clean图的导出子图如图4：

Figure 4. The induced subgraph of the nil-clean graph of ${\mathbb{Z}}_{11}$

图4. ${\mathbb{Z}}_{11}$ 的nil-clean图的导出子图

因为$3\nmid \left(11-1\right)$ ，所以由定理3.1，$\left|C\right|=\lceil \frac{11-1}{3}\rceil =4$ ，观察图4可知，$C=\left\{\overline{1},\overline{9},\overline{4},\overline{6}\right\}$ 是${\Gamma }_{NC}\left({\mathbb{Z}}_{11}\right)$ 的一

个完备码。

现在我们引入约化图的定义，方便接下来定理的证明。

定义3.3 [13]设$G$ 是一个简单图，定义点集$V\left(G\right)$ 上的等价关系$\sim$ ：对任意两点$u,v\in V\left(G\right)$ ，$u\sim v$ 当且仅当它们的开邻域相等。图$G$ 的约化图$G_{red}$ 有点集$V\left(G_{red}\right)=\left\{\left[v\right]\mid v\in V(G)\right\}$ ，(其中$\left[v\right]$ 是点$v$ 所在的等价类)，任意两个不同点$\left[u\right]$ 和$\left[v\right]$ 在$G_{red}$ 中是邻接的当且仅当$u$ 和$v$ 在$G$ 中是邻接的。

定理3.4 设${\Gamma }_{NC}\left({\mathbb{Z}}_{p^k}\right)$ 是环${\mathbb{Z}}_{p^k}$ 的nil-clean图的导出子图，其中$p$ 是一个素数，$k$ 是正整数，且$C$ 为该图的完备码。

1) 若$p=2,3$ ，则$\left|C\right|=1$ 。

2) 若$p\ne 2,3$ ，则完备码不存在。

证明：因为${\mathbb{Z}}_{p^k}$ 是交换的局部环，它有唯一的极大理想$\left(\overline{p}\right)=Nil\left({\mathbb{Z}}_{p^k}\right)$ ，且$Id\left({\mathbb{Z}}_{p^k}\right)=\left\{\overline{0},\overline{1}\right\}$ ，所以，$NC\left({\mathbb{Z}}_{p^k}\right)=\left(\overline{p}\right)\cup \overline{1}+\left(\overline{p}\right)$ 。

1) 当$p=2$ 时，$NC\left({\mathbb{Z}}_{2^k}\right)=\left(\overline{2}\right)\cup \overline{1}+\left(\overline{2}\right)={\mathbb{Z}}_{2^k}$ ，即环${\mathbb{Z}}_{2^k}$ 中每个元素都是nil-clean元，从而${\mathbb{Z}}_{2^k}$ 是一个nil-clean环，所以$G_{NC}\left({\mathbb{Z}}_{2^k}\right)$ 是一个完全图，这说明导出子图${\Gamma }_{NC}\left({\mathbb{Z}}_{2^k}\right)$ 也是一个完全图。因此，${\mathbb{Z}}_{2^k}$ 中任意一点都是图${\Gamma }_{NC}\left({\mathbb{Z}}_{2^k}\right)$ 的一个完备码，此时，$\left|C\right|=1$ 。

当$p=3$ 时，$NC\left({\mathbb{Z}}_{3^k}\right)=\left(\overline{3}\right)\cup \overline{1}+\left(\overline{3}\right)$ ，$V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{3^k}\right)\right)=U\left({\mathbb{Z}}_{3^k}\right)=\overline{1}+\left(\overline{3}\right)\cup \overline{2}+\left(\overline{3}\right)$ ，图${\Gamma }_{NC}\left({\mathbb{Z}}_{3^k}\right)$ 的约化图如图5：

Figure 5. The reduced graph of the induced subgraph of the nil-clean graph of ${\mathbb{Z}}_{3^k}$

图5. ${\mathbb{Z}}_{3^k}$ 的nil-clean图的导出子图的约化图

因为对任意两点$x_1,x_2\in \overline{1}+\left(\overline{3}\right)$ ，$x_1+x_2=\overline{2}+\left(\overline{3}\right)\notin NC\left({\mathbb{Z}}_{3^k}\right)$ ，对任意两点$y_1,y_2\in \overline{2}+\left(\overline{3}\right)$ ，$y_1+y_2=\overline{1}+\left(\overline{3}\right)\in NC\left({\mathbb{Z}}_{3^k}\right)$ ，所以图5中空心点表示该等价类中所有代表元在原图中是互不相连的，实心点表示该等价类中所有代表元在原图中是两两相连的。这表明，对$\overline{2}+\left(\overline{3}\right)$ 中任意一个代表元$x$ ，点$x$ 在${\Gamma }_{NC}\left({\mathbb{Z}}_{3^k}\right)$ 中的半径为1的闭邻域$S_1\left(x\right)=\left\{\overline{1}+\left(\overline{3}\right),\overline{2}+\left(\overline{3}\right)\right\}=V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{3^k}\right)\right)$ ，因此，$\left|C\right|=1$ 。

若$p\ne 2,3$ ，则$V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{p^k}\right)\right)=U\left({\mathbb{Z}}_{p^k}\right)=\overline{1}+\left(\overline{p}\right)\cup \overline{2}+\left(\overline{p}\right)\cup \cdots \cup \overline{p-1}+\left(\overline{p}\right)$ 且$NC\left({\mathbb{Z}}_{p^k}\right)=\left(\overline{p}\right)\cup \overline{1}+\left(\overline{p}\right)$ ，所以${\Gamma }_{NC}\left({\mathbb{Z}}_{p^k}\right)$ 的约化图如图6：

Figure 6. The reduced graph of the induced subgraph of the nil-clean graph of ${\mathbb{Z}}_{p^k}$

图6. ${\mathbb{Z}}_{p^k}$ 的nil-clean图的导出子图的约化图

与图5类似，每个空心点表示该等价类中所有代表元在原图中互不相连，实心点代表该等价类中所有代表元在原图中两两相连。假设存在完备码$C\subseteq V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{p^k}\right)\right)$ ，则$\overline{1}+\left(\overline{p}\right)\cup \overline{p-1}+\left(\overline{p}\right)$ 中至少有一点属于$C$ ，否则对任意一点$x\in \overline{1}+\left(\overline{p}\right)$ ，$x\notin \cup S_1\left(c_i\right)$ ，即$\cup S_1\left(c_i\right)\ne V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{p^k}\right)\right)$ ，其中$c_i$ 取遍$C$ 中所有元素。

假设只存在一点$x_1\in \overline{1}+\left(\overline{p}\right)\cup \overline{p-1}+\left(\overline{p}\right)$ ，使得$x_1\in C$ 。若$x_1\in \overline{1}+\left(\overline{p}\right)$ ，则对任意$x_2\in \overline{1}+\left(\overline{p}\right)\setminus \left\{x_1\right\}$ ，$x_2\notin \cup S_1\left(c_i\right)$ ，即$\cup S_1\left(c_i\right)\ne V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{p^k}\right)\right)$ ，与完备码定义矛盾，所以$x_1\notin \overline{1}+\left(\overline{p}\right)$ ；若$x_1\in \overline{p-1}+\left(\overline{p}\right)$ ，则此时至少存在一点$x_2\in \overline{2}+\left(\overline{p}\right)$ ，使得$x_2\in C$ ，否则对任意一点$x_3\in \overline{p-1}+\left(\overline{p}\right)\setminus \left\{x_1\right\}$ ，$x_3\notin \cup S_1\left(c_i\right)$ 。但如果存在$x_2\in \overline{2}+\left(\overline{p}\right)$ ，则$S_1\left(x_1\right)\cap S_1\left(x_2\right)=\left\{x_1,x_2\right\}\ne \varnothing$ 与完备码定义矛盾，所以$x_1\notin \overline{p-1}+\left(\overline{p}\right)$ 。

假设至少存在两点$x,y\in \overline{1}+\left(\overline{p}\right)\cup \overline{p-1}+\left(\overline{p}\right)$ ，使得$x,y\in C$ ，则$S_1\left(x\right)\cap S_1\left(y\right)\ne \varnothing$ ，这与完备码的定义矛盾，因此，图${\Gamma }_{NC}\left({\mathbb{Z}}_{p^k}\right)$ 中不存在完备码。

例3.5 设${\Gamma }_{NC}\left(R\right)$ 为环$R$ 的nil-clean图的导出子图，且$C$ 是它的完备码。

设$R={\mathbb{Z}}_{32}$ ，则$V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{32}\right)\right)=U\left({\mathbb{Z}}_{32}\right)=\overline{1}+\left(\overline{2}\right)=\left\{\overline{1},\overline{3},\overline{5},\overline{7},\cdots ,\overline{29},\overline{31}\right\}$ 且$NC\left({\mathbb{Z}}_{32}\right)={\mathbb{Z}}_{32}$ ，所以${\mathbb{Z}}_{32}$ 的nil-clean图的导出子图是一个完全图，见图7：

Figure 7. The induced subgraph of the nil-clean graph of ${\mathbb{Z}}_{32}$

图7. ${\mathbb{Z}}_{32}$ 的nil-clean图的导出子图

由定理3.4，$\left|C\right|=1$ ，观察图7可知，对任意一点$x\in V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{32}\right)\right)$ ，$S_1\left(x\right)=V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{32}\right)\right)$ ，那么$C=\left\{x\right\}$ 。

设$R={\mathbb{Z}}_{27}$ ，则$V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{27}\right)\right)=U\left({\mathbb{Z}}_{27}\right)=\overline{1}+\left(\overline{3}\right)\cup \overline{2}+\left(\overline{3}\right)$ 且$NC\left({\mathbb{Z}}_{27}\right)=\left(\overline{3}\right)\cup \overline{1}+\left(\overline{3}\right)$ ，图8为${\mathbb{Z}}_{27}$ 的nil-clean图的导出子图：

Figure 8. The induced subgraph of the nil-clean graph of ${\mathbb{Z}}_{27}$

图8. ${\mathbb{Z}}_{27}$ 的nil-clean图的导出子图

由定理3.4，$\left|C\right|=1$ ，由图8知，对任意一点$x\in \left\{\overline{2},\overline{5},\overline{8},\overline{11},\overline{14},\overline{17},\overline{20},\overline{23},\overline{26}\right\}$ ，$S_1\left(x\right)=V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{27}\right)\right)$ ，所以$C=\left\{x\right\}$ 。

设$R={\mathbb{Z}}_{25}$ ，则$V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{25}\right)\right)=U\left({\mathbb{Z}}_{25}\right)=\overline{1}+\left(\overline{5}\right)\cup \overline{2}+\left(\overline{5}\right)\cup \overline{3}+\left(\overline{5}\right)\cup \overline{4}+\left(\overline{5}\right)$ 且$NC\left({\mathbb{Z}}_{25}\right)=\left(\overline{5}\right)\cup \overline{1}+\left(\overline{5}\right)$ ，${\mathbb{Z}}_{25}$ 的nil-clean图的导出子图如图9：

Figure 9. The induced subgraph of the nil-clean graph of ${\mathbb{Z}}_{25}$

图9. ${\mathbb{Z}}_{25}$ 的nil-clean图的导出子图

由定理3.4，该图不存在完备码。下面给出半径为1的每个点的闭邻域：

对任意一点$x_1\in \overline{1}+\left(\overline{5}\right)=\left\{\overline{1},\overline{6},\overline{11},\overline{16},\overline{21}\right\}$ ，

$S_1\left(x_1\right)=\left\{x_1\right\}\cup \overline{4}+\left(\overline{5}\right)=\left\{x_1,\overline{4},\overline{9},\overline{14},\overline{19},\overline{24}\right\}$ ，

对任意一点$x_2\in \overline{2}+\left(\overline{5}\right)=\left\{\overline{2},\overline{7},\overline{12},\overline{17},\overline{22}\right\}$ ，

$S_1\left(x_2\right)=\left\{x_2\right\}\cup \overline{3}+\left(\overline{5}\right)\cup \overline{4}+\left(\overline{5}\right)=\left\{x_2,\overline{3},\overline{4},\overline{8},\overline{9},\overline{13},\overline{14},\overline{18},\overline{19},\overline{23},\overline{24}\right\}$ ，

对任意一点$x_3\in \overline{3}+\left(\overline{5}\right)=\left\{\overline{3},\overline{8},\overline{13},\overline{18},\overline{23}\right\}$ ，

$S_1\left(x_3\right)=\overline{2}+\left(\overline{5}\right)\cup \overline{3}+\left(\overline{5}\right)=\left\{\overline{2},\overline{3},\overline{7},\overline{8},\overline{12},\overline{13},\overline{17},\overline{18},\overline{22},\overline{23}\right\}$ ，

对任意一点$x_4\in \overline{4}+\left(\overline{5}\right)=\left\{\overline{4},\overline{9},\overline{14},\overline{19},\overline{24}\right\}$ ，

$S_1\left(x_4\right)=\left\{x_4\right\}\cup \overline{1}+\left(\overline{5}\right)\cup \overline{2}+\left(\overline{5}\right)=\left\{x_4,\overline{1},\overline{2},\overline{6},\overline{7},\overline{11},\overline{12},\overline{16},\overline{17},\overline{21},\overline{22}\right\}$ 。

我们发现不存在码$C\subseteq V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{25}\right)\right)$ ，使得$C$ 为${\Gamma }_{NC}\left({\mathbb{Z}}_{25}\right)$ 中的完备码。

定理3.6 设${\Gamma }_{NC}\left({\mathbb{Z}}_{2p}\right)$ 是环${\mathbb{Z}}_{2p}$ 的nil-clean图的导出子图，其中$p$ 是一个奇素数，且$C$ 为该图的完备

码，则$\left|C\right|=\lceil \frac{p-1}{3}\rceil$ 。

证明：当$p$ 是一个奇素数时，$Nil\left({\mathbb{Z}}_{2p}\right)=\left\{\overline{0}\right\}$ ，$Id\left({\mathbb{Z}}_{2p}\right)=\left\{\overline{0},\overline{1},\overline{p},\overline{p+1}\right\}$ ，所以$NC\left({\mathbb{Z}}_{2p}\right)=\left\{\overline{0},\overline{1},\overline{p},\overline{p+1}\right\}$ 。$V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{2p}\right)\right)=U\left({\mathbb{Z}}_{2p}\right)=\left\{\overline{1},\overline{3},\overline{5},\overline{7},\cdots ,\overline{p-2},\overline{p+2},\cdots ,\overline{2p-3},\overline{2p-1}\right\}$ ，因为$V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{2p}\right)\right)$ 中都是奇数点，则$V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{2p}\right)\right)$ 中任意两点之和都是偶数，所以$E\left({\Gamma }_{NC}\left({\mathbb{Z}}_{2p}\right)\right)=\left\{\left(x,y\right)\mid x,y\in V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{2p}\right)\right),x+y=\overline{0}或\overline{p+1}\right\}$ 。${\mathbb{Z}}_{2p}$ 的nil-clean图的导出子图如图10：

Figure 10. The induced subgraph of the nil-clean graph of ${\mathbb{Z}}_{2p}$

图10. ${\mathbb{Z}}_{2p}$ 的nil-clean图的导出子图

因为$\overline{1}+\overline{p}=\overline{p+1}$ ，$\overline{1}+\overline{2p-1}=\overline{0}$ ，$v_3+v_3=\overline{p+1}$ ，$v_2+v_3=\overline{0}$ ，但是$\overline{p}\notin V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{2p}\right)\right)$ 且本文只考虑简单图，因此点$\overline{1}$ 只与$\overline{2p-1}$ 邻接，点$v_3$ 只与$v_2$ 邻接。而对任意一点$\overline{v}\in V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{2p}\right)\right)\setminus \left\{\overline{1},\overline{v_3}\right\}$ ，$\overline{v}+\overline{0-v}=\overline{0}$ ，$\overline{v}+\overline{p+1-v}=\overline{p+1}$ ，所以点$\overline{v}$ 只与$\overline{-v}$ 和$\overline{p+1-v}$ 邻接。由图10知，${\Gamma }_{NC}\left({\mathbb{Z}}_{2p}\right)$ 是一个有$p-1$ 个点的路径，同定理3.1的证明，可以得到图${\Gamma }_{NC}\left({\mathbb{Z}}_{2p}\right)$ 中完备码的大小，结论得证。

例3.7 设${\Gamma }_{NC}\left(R\right)$ 是环$R$ 的nil-clean图的导出子图，且$C$ 是它的完备码。当$R={\mathbb{Z}}_{34}$ 时，$V\left({\Gamma }_{NC}\left({\mathbb{Z}}_{34}\right)\right)=U\left({\mathbb{Z}}_{34}\right)=\left\{\overline{1},\overline{3},\overline{5},\overline{7},\overline{9},\overline{11},\overline{13},\overline{15},\overline{19},\overline{21},\overline{23},\overline{25},\overline{27},\overline{29},\overline{31},\overline{33}\right\}$ 且$NC\left({\mathbb{Z}}_{34}\right)=\left\{\overline{0},\overline{1},\overline{17},\overline{18}\right\}$ ，则${\mathbb{Z}}_{34}$ 的nil-clean图的导出子图如图11：

Figure 11. The induced subgraph of the nil-clean graph of ${\mathbb{Z}}_{34}$

图11. ${\mathbb{Z}}_{34}$ 的nil-clean图的导出子图

由定理3.6知，$\left|C\right|=\lfloor \frac{17-1}{3}\rfloor +1=6$ 。观察图11可知，$C=\left\{\overline{1},\overline{15},\overline{21},\overline{29},\overline{7},\overline{9}\right\}$ 是${\Gamma }_{NC}\left({\mathbb{Z}}_{34}\right)$ 的完备码。

定理3.8 设${\Gamma }_{NC}\left({\mathbb{Z}}_{pq}\right)$ 是环${\mathbb{Z}}_{pq}$ 的nil-clean图的导出子图，其中$p$ 和$q$ 是两个互异的奇素数，则图${\Gamma }_{NC}\left({\mathbb{Z}}_{pq}\right)$ 中不存在完备码。

证明：因为$p$ 和$q$ 是两个互异的奇素数，所以${\mathbb{Z}}_{pq}\cong {\mathbb{Z}}_p\times {\mathbb{Z}}_q$ ，从而${\Gamma }_{NC}\left({\mathbb{Z}}_{pq}\right)\cong {\Gamma }_{NC}\left({\mathbb{Z}}_p\times {\mathbb{Z}}_q\right)$ 。$V\left({\Gamma }_{NC}\left({\mathbb{Z}}_p\times {\mathbb{Z}}_q\right)\right)=U\left({\mathbb{Z}}_p\times {\mathbb{Z}}_q\right)=\left\{\left(u,v\right)\mid u\ne 0且v\ne 0,u\in {\mathbb{Z}}_p,v\in {\mathbb{Z}}_q\right\}$ ， $NC\left({\mathbb{Z}}_p\times {\mathbb{Z}}_q\right)=\left\{\left(\overline{0},\overline{0}\right),\left(\overline{0},\overline{1}\right),\left(\overline{1},\overline{0}\right),\left(\overline{1},\overline{1}\right)\right\}$ ，则${\mathbb{Z}}_p\times {\mathbb{Z}}_q$ 的nil-clean图的导出子图如图12：

Figure 12. The induced subgraph of the nil-clean graph of ${\mathbb{Z}}_p\times {\mathbb{Z}}_q$

图12. ${\mathbb{Z}}_p\times {\mathbb{Z}}_q$ 的nil-clean图的导出子图

我们首先讨论${\Gamma }_{NC}\left({\mathbb{Z}}_3\times {\mathbb{Z}}_q\right)\left(q>3\right)$ 的完备码，我们给图${\Gamma }_{NC}\left({\mathbb{Z}}_3\times {\mathbb{Z}}_q\right)$ 重新标号得到图13：

Figure 13. The relabeled induced subgraph of the nil-clean graph of ${\mathbb{Z}}_3\times {\mathbb{Z}}_q$

图13. 重新标号后的${\mathbb{Z}}_3\times {\mathbb{Z}}_q$ 的nil-clean图的导出子图

假设${\Gamma }_{NC}\left({\mathbb{Z}}_3\times {\mathbb{Z}}_q\right)$ 中存在完备码$C$ ，则$x_{11}\in C$ 或$x_{22}\in C$ ，否则$x_{11}\notin \cup S_1\left(c_i\right)$ ，即$\cup S_1\left(c_i\right)\ne V\left({\Gamma }_{NC}\left({\mathbb{Z}}_3\times {\mathbb{Z}}_q\right)\right)$ ，其中$c_i$ 取遍$C$ 中所有元素。

如果$x_{22}\in C$ ，易知$S_1\left(x_{22}\right)=\left\{x_{11},x_{13},x_{21},x_{22},x_{23}\right\}$ ，那么$x_{11},x_{12},x_{13},x_{21},x_{23}\notin C$ ，否则存在点$v\in \left\{x_{11},x_{12},x_{13},x_{21},x_{23}\right\}$ ，使得$S_1\left(x_{22}\right)\cap S_1\left(v\right)\ne \varnothing$ ，但此时$x_{12}\notin \cup S_1\left(c_i\right)$ ，则$\cup S_1\left(c_i\right)\ne V\left({\Gamma }_{NC}\left({\mathbb{Z}}_3\times {\mathbb{Z}}_q\right)\right)$ ，与完备码定义矛盾，所以$x_{22}\notin C$ 。

如果$x_{11}\in C$ ，易知$S_1\left(x_{11}\right)=\left\{x_{11},x_{22}\right\}$ ，那么$x_{13},x_{21},x_{22},x_{23}\notin C$ ，否则存在$v\in \left\{x_{13},x_{21},x_{22},x_{23}\right\}$ ，使得$S_1\left(x_{11}\right)\cap S_1\left(v\right)\ne \varnothing$ ，而为了保证$x_{12},x_{13}\in \cup S_1\left(c_i\right)$ ，只能$x_{12},x_{24}\in C$ ，但是$x_{23}\in S_1\left(x_{12}\right)\cap S_1\left(x_{24}\right)$ ，与完备码定义矛盾，所以$x_{11}\notin C$ 。综上，${\Gamma }_{NC}\left({\mathbb{Z}}_3\times {\mathbb{Z}}_q\right)$ 中不存在完备码。

接下来讨论${\Gamma }_{NC}\left({\mathbb{Z}}_p\times {\mathbb{Z}}_q\right)\left(p>3,q>5\right)$ 的完备码，将图${\Gamma }_{NC}\left({\mathbb{Z}}_p\times {\mathbb{Z}}_q\right)$ 重新标号后截取一部分得到图14：

Figure 14. A part obtained by extracting the relabeled induced subgraph of the nil-clean graph of ${\mathbb{Z}}_p\times {\mathbb{Z}}_q$

图14. 截取重新标号后的${\mathbb{Z}}_p\times {\mathbb{Z}}_q$ 的nil-clean图的导出子图所得的一部分

假设${\Gamma }_{NC}\left({\mathbb{Z}}_p\times {\mathbb{Z}}_q\right)\left(p>3,q>5\right)$ 中存在完备码$C$ ，则$y_{11},y_{21},y_{22}$ 中必有一点属于$C$ ，否则$y_{11}\notin \cup S_1\left(c_i\right)$ ，即$\cup S_1\left(c_i\right)\ne V\left({\Gamma }_{NC}\left({\mathbb{Z}}_p\times {\mathbb{Z}}_q\right)\right)$ ，其中$c_i$ 取遍$C$ 中所有元素。

(1) 若$y_{11}\in C$ ，则$y_{12},y_{13},y_{21},y_{22},y_{31},y_{32}\notin C$ ，否则存在$v\in \left\{y_{12},y_{13},y_{21},y_{22},y_{31},y_{32}\right\}$ ，使得$S_1\left(v\right)\cap S_1\left(y_{11}\right)\ne \varnothing$ 。因为要使得$y_{12}\in \cup S_1\left(c_i\right)$ ，所以只能$y_{23}\in C$ ，则$y_{41}\notin C$ ，否则$S_1\left(y_{41}\right)\cap S_1\left(y_{23}\right)=\left\{y_{32}\right\}\ne \varnothing$ 。又因为要使得$y_{31}\in \cup S_1\left(c_i\right)$ ，所以只能$y_{42}\in C$ ，则$y_{24}\notin C$ ，否则$S_1\left(y_{24}\right)\cap S_1\left(y_{42}\right)=\left\{y_{33}\right\}\ne \varnothing$ ，此时我们发现$y_{13},y_{22},y_{24}\notin C$ ，这说明$y_{13}\notin \cup S_1\left(c_i\right)$ ，与完备码定义矛盾，所以$y_{11}\notin C$ 。

(2) 若$y_{21}\in C$ ，则$y_{11},y_{22},y_{31},y_{42}\notin C$ ，否则存在$v_1\in \left\{y_{11},y_{22},y_{31},y_{42}\right\}$ ，使得$S_1\left(v_1\right)\cap S_1\left(y_{21}\right)\ne \varnothing$ 。因为要满足$y_{13}\in \cup S_1\left(c_i\right)$ ，所以只能$y_{13}\in C$ 或$y_{24}\in C$ 。

如果$y_{24}\in C$ ，那么$y_{13},y_{33}\notin C$ ，否则存在$v_2\in \left\{y_{13},y_{33}\right\}$ ，使得$S_1\left(v_2\right)\cap S_1\left(y_{24}\right)\ne \varnothing$ ，这时我们发现$y_{11},y_{13},y_{22},y_{31},y_{33}\notin C$ ，那么$y_{22}\notin \cup S_1\left(c_i\right)$ ，与完备码定义矛盾，所以$y_{24}\notin C$ 。

如果$y_{13}\in C$ ，则$y_{15},y_{24},y_{33}\notin C$ ，否则存在$v_3\in \left\{y_{15},y_{24},y_{33}\right\}$ ，使得$S_1\left(v_3\right)\cap S_1\left(y_{13}\right)\ne \varnothing$ ，因为要保证$y_{33}\in \cup S_1\left(c_i\right)$ ，则只能$y_{44}\in C$ ，则$y_{26}\notin C$ ，否则$S_1\left(y_{26}\right)\cap S_1\left(y_{44}\right)=\left\{y_{35}\right\}\ne \varnothing$ ，此时$y_{15},y_{24},y_{26}\notin C$ ，那么$y_{15}\notin \cup S_1\left(c_i\right)$ ，与完备码定义矛盾，所以$y_{13}\notin C$ 。根据以上得出$y_{21}\notin C$ 。

(3) 若$y_{22}\in C$ ，则$y_{11},y_{21},y_{31},y_{41}\notin C$ ，否则存在$v_1\in \left\{y_{11},y_{21},y_{31},y_{41}\right\}$ ，使得$S_1\left(v_1\right)\cap S_1\left(y_{22}\right)\ne \varnothing$ 。因为要保证$y_{21}\in \cup S_1\left(c_i\right)$ ，只能$y_{12}\in C$ 或$y_{32}\in C$ 。

如果$y_{32}\in C$ ，则$y_{12},y_{23}\notin C$ ，否则存在$v_2\in \left\{y_{12},y_{23}\right\}$ ，使得$S_1\left(v_2\right)\cap S_1\left(y_{32}\right)\ne \varnothing$ ，而此时$y_{12},y_{21},y_{23}\notin C$ ，那么$y_{12}\notin \cup S_1\left(c_i\right)$ ，这与完备码定义矛盾，所以$y_{32}\notin C$ 。

如果$y_{12}\in C$ ，则$y_{14},y_{23},y_{32}\notin C$ ，否则存在$v_3\in \left\{y_{14},y_{23},y_{32}\right\}$ ，使得$S_1\left(v_3\right)\cap S_1\left(y_{12}\right)\ne \varnothing$ ，因为要使得$y_{32}\in \cup S_1\left(c_i\right)$ ，则只能$y_{43}\in C$ ，从而$y_{25}\notin C$ ，否则$S_1\left(y_{25}\right)\cap S_1\left(y_{43}\right)\ne \varnothing$ ，此时$y_{14},y_{23},y_{25}\notin C$ ，这说明$y_{14}\notin \cup S_1\left(c_i\right)$ ，与完备码定义矛盾，所以$y_{12}\notin C$ 。根据以上得$y_{22}\notin C$ 。

综上，$y_{11},y_{21},y_{22}\notin C$ ，则$y_{11}\notin \cup S_1\left(c_i\right)$ ，从而$\cup S_1\left(c_i\right)\ne V\left({\Gamma }_{NC}\left({\mathbb{Z}}_p\times {\mathbb{Z}}_q\right)\right)$ ，因此，图${\Gamma }_{NC}\left({\mathbb{Z}}_p\times {\mathbb{Z}}_q\right)$ 中不存在完备码。

4. 小结和展望

本文基于nil-clean图的概念，构造了以单位集为点集的一些环的nil-clean图的导出子图并给出其完备码的大小。我们得到以下结论：当$n=p$ 和$2p$ (其中$p$ 是一个奇素数)时，图${\Gamma }_{NC}\left({\mathbb{Z}}_n\right)$ 是一条路径，其完

备码大小为$\lceil \frac{p-1}{3}\rceil$ ；当$n=2^k$ 和$3^k$ (其中$k$ 为正整数)时，${\Gamma }_{NC}\left({\mathbb{Z}}_n\right)$ 中完备码的大小为1；当$n=p^k$ (其中

$p>3$ 为素数)和$pq$ (其中$p,q$ 是两个互异奇素数)时，${\Gamma }_{NC}\left({\mathbb{Z}}_n\right)$ 中不存在完备码。当然，对于一般的$n$ 值，我们还没有给出图${\Gamma }_{NC}\left({\mathbb{Z}}_n\right)$ 中完备码的相关结论，这也是需要我们进一步研究的问题。

基金项目

本论文由国家自然科学基金(项目编号：12261001，12461001)资助。

NOTES

^*通讯作者。