若干凸多胞体图的容错度量维数

Fault-Tolerant Metric Dimension of Some Convex Polytope Graphs

摘要: 图的容错度量维数的概念是由Hernand等人于2008年提出的，它是度量维数的一个新变形，也是图论和组合优化交叉研究的内容，在机器导航、医药化学、组合优化和图像处理等领域有着广泛的应用。由于图的容错度量维数比其度量维数有更好的适应性，所以图的容错度量维数的研究越来越受到人们的关注。对于给定的图和正整数k确定该图的容错度量维数是否不超过k是NP-难的。本文通过构作凸多胞体图$B_n$ ，$C_n$ 和$E_n$ 的容错解析集，得到了当$n\ge 6$ 时凸多胞体图$B_n$ ，$C_n$ 和$E_n$ 的容错度量维数都为4。这些成果在图论和组合优化中具有重要的理论价值，并在网络电信和图像处理等方面有重要应用。

Abstract: The concept of fault-tolerant metric dimension of a graph was introduced by Hernand et al. in 2008. It is a distortion of the metric dimension of a graph and is the intersection of graph theory and combinatorial optimization. It has been widely used in many fields, such as machine navigation, medicinal chemistry, combinatorial optimization and image processing. The study of fault-tolerant metric dimension of a graph gets more and more attention from people, since it has better adaptability than the metric dimension of a graph. For a given graph and a positive integer k, deciding whether its fault-tolerant metric dimension is less than or equal to k is an NP-complete problem. In this paper, by constructing the fault-tolerant resolving sets of convex polytope graphs $B_n$ , $C_n$ and $E_n$ , respectively, we obtain their fault-tolerant metric dimensions are all 4 for $n\ge 6$ . These results have theoretical value in graph theory and combinatorial optimization and have important applications in network telecommunications, image processing, etc.

1. 引言

设图G是一个简单无向的连通图，$V\left(G\right)$ 是图G的顶点集，$E\left(G\right)$ 是图G的边集。设顶点$u,v\in V\left(G\right)$ ，顶点u和v之间最短路的长度被称为顶点$u,v$ 之间的距离$d\left(u,v\right)$ 。设W是$V\left(G\right)$ 的一个子集，若对于任意两个顶点$v_1,v_2\in V\left(G\right)$ 都存在$x\in W$ 使得$d\left(x,v_1\right)\ne d\left(x,v_2\right)$ ，则称W是图G的解析集。称基数最小的解析集为图G的度量基，其基数叫做图G的度量维数，记作$\dim \left(G\right)$ 。图的度量维数作为图论和组合优化领域的重要组成部分，渐渐地成为了数学以及其他领域学者的热门话题。1953年，Blumenthal [1]引入了一般空间中度量维数的概念，在此之后，Slater [2]在1975年为了确定网络中入侵者的位置，首次提出了解析集和度量维数的概念。随后越来越多的学者加入图度量维数的研究中，目前已经在机器导肮[3]、医药化学[4]、组合优化[5]以及图像处理[6]等领域有着广泛的应用。

Hernand等人[7]提出了度量维数的一个新的变形——容错度量维数。其定义如下：对于图G的一个解析集$W_f$ ，对于任意的$w\in W_f$ ，如果$W_f\backslash \left\{w\right\}$ 仍是一个解析集，则称$W_f$ 是图G的容错解析集。称基数最小的容错解析集为图G的容错度量基，其基数叫做图G的容错度量维数，记作${\dim }_f\left(G\right)$ 。对于给定的图G和正整数k，确定${\dim }_f\left(G\right)\le k$ 是NP-难的。容错度量维数在网络电信[8]、药物化学[9] [10]以及机器导航[11]等领域有着进一步的应用。因此，研究图容错度量维数尤其重要。本文研究了凸多胞体图$B_n$ 、$C_n$ 以及$E_n$ 的容错度量维数。

2. 凸多胞体图$B_n$ 的容错度量维数

首先介绍凸多胞体图$B_n$ ，凸多胞体图$B_n$ 有$5n$ 个点和$9n$ 条边，如图1所示。图$B_n$ 的顶点集和边集定义如下：

$V\left(B_n\right)=\{a_i,b_i,c_i,d_i,f_i:1\le i\le n\};$

$\begin{array}{c}E\left(B_n\right)=\{a_i{a}_{i+1},b_i{b}_{i+1},d_i{d}_{i+1},f_i{f}_{i+1}:1\le i\le n\}\\ \cup \{a_i{b}_i,b_i{c}_i,b_{i+1}{c}_i,c_i{d}_i,d_i{f}_i:1\le i\le n\}.\end{array}$

Figure 1. The convex polytope graph B_n

图1. 凸多胞体图B_n

引理1.1 [12] 设$G=\left(V,E\right)$ 是一个简单无向的连通图，则${\dim }_f\left(G\right)\ge \dim \left(G\right)+1$ 。

引理1.2 [13] 当$n\ge 6$ 时，凸多胞体图$B_n$ 的度量维数$\dim \left(B_n\right)=3$ 。

定理1.1 当$n\ge 6$ 时，凸多胞体图$B_n$ 的容错度量维数${\dim }_f\left(B_n\right)=4$ 。

证明：当$n\ge 6$ 时，设$W_f=\left\{a_1,a_2,a_{\lfloor \frac{n}{2}\rfloor +1},a_{\lfloor \frac{n}{2}\rfloor +2}\right\}$ 。下面证明$W_f$ 是凸多胞体图$B_n$ 的一个容错解析集。$B_n$ 中的每个顶点关于$W_f$ 的度量表示如下：

$r\left(a_i|W_f\right)=\{\begin{array}{ll}\left(0,1,\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil -1\right),\hfill & i=1;\hfill \\ \left(i-1,i-2,\lfloor \frac{n}{2}\rfloor -i+1,\lfloor \frac{n}{2}\rfloor -i+2\right),\hfill & 2\le i\le \lfloor \frac{n}{2}\rfloor +1;\hfill \\ \left(\lceil \frac{n}{2}\rceil -1,\lfloor \frac{n}{2}\rfloor ,1,0\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +2;\hfill \\ \left(n-i+1,n-i+2,i-\lfloor \frac{n}{2}\rfloor -1,i-\lfloor \frac{n}{2}\rfloor -2\right),\hfill & \lfloor \frac{n}{2}\rfloor +3\le i\le n;\hfill \end{array}$ (1)

$r\left(b_i|W_f\right)=\{\begin{array}{ll}\left(1,2,\lfloor \frac{n}{2}\rfloor +1,\lceil \frac{n}{2}\rceil \right),\hfill & i=1;\hfill \\ \left(i,i-1,\lfloor \frac{n}{2}\rfloor -i+2,\lfloor \frac{n}{2}\rfloor -i+3\right),\hfill & 2\le i\le \lfloor \frac{n}{2}\rfloor +1;\hfill \\ \left(\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor +1,2,1\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +2;\hfill \\ \left(n-i+2,n-i+3,i-\lfloor \frac{n}{2}\rfloor ,i-\lfloor \frac{n}{2}\rfloor -1\right),\hfill & \lfloor \frac{n}{2}\rfloor +3\le i\le n;\hfill \end{array}$ (2)

$r\left(c_i|W_f\right)=\{\begin{array}{ll}\left(2,2,\lfloor \frac{n}{2}\rfloor +1,\lceil \frac{n}{2}\rceil +1\right),\hfill & i=1;\hfill \\ \left(i+1,i,\lfloor \frac{n}{2}\rfloor -i+2,\lfloor \frac{n}{2}\rfloor -i+3\right),\hfill & 2\le i\le \lfloor \frac{n}{2}\rfloor ;\hfill \\ \left(\lceil \frac{n}{2}\rceil +1,\lfloor \frac{n}{2}\rfloor +1,2,2\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +1;\hfill \\ \left(n-i+2,n-i+3,i-\lfloor \frac{n}{2}\rfloor +1,i-\lfloor \frac{n}{2}\rfloor \right),\hfill & \lfloor \frac{n}{2}\rfloor +2\le i\le n;\hfill \end{array}$ (3)

$r\left(d_i|W_f\right)=\{\begin{array}{ll}\left(3,3,\lfloor \frac{n}{2}\rfloor +2,\lceil \frac{n}{2}\rceil +2\right),\hfill & i=1;\hfill \\ \left(i+2,i+1,\lfloor \frac{n}{2}\rfloor -i+3,\lfloor \frac{n}{2}\rfloor -i+4\right),\hfill & 2\le i\le \lfloor \frac{n}{2}\rfloor ;\hfill \\ \left(\lceil \frac{n}{2}\rceil +2,\lfloor \frac{n}{2}\rfloor +2,3,3\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +1;\hfill \\ \left(n-i+3,n-i+4,i-\lfloor \frac{n}{2}\rfloor +2,i-\lfloor \frac{n}{2}\rfloor +1\right),\hfill & \lfloor \frac{n}{2}\rfloor +2\le i\le n;\hfill \end{array}$ (4)

$r\left(f_i|W_f\right)=\{\begin{array}{ll}\left(4,4,\lfloor \frac{n}{2}\rfloor +3,\lceil \frac{n}{2}\rceil +2\right),\hfill & i=1;\hfill \\ \left(4,4,\lfloor \frac{n}{2}\rfloor +2,\lceil \frac{n}{2}\rceil +3\right),\hfill & i=2;\hfill \\ \left(i+2,i+1,\lfloor \frac{n}{2}\rfloor -i+4,\lfloor \frac{n}{2}\rfloor -i+5\right),\hfill & 3\le i\le \lfloor \frac{n}{2}\rfloor ;\hfill \\ \left(\lceil \frac{n}{2}\rceil +3,\lfloor \frac{n}{2}\rfloor +2,4,4\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +1;\hfill \\ \left(\lceil \frac{n}{2}\rceil +2,\lfloor \frac{n}{2}\rfloor +3,4,4\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +2;\hfill \\ \left(n-i+4,n-i+5,i-\lfloor \frac{n}{2}\rfloor +2,i-\lfloor \frac{n}{2}\rfloor +1\right),\hfill & \lfloor \frac{n}{2}\rfloor +3\le i\le n;\hfill \end{array}$ (5)

从度量表示(1)~(5)可以看出，$V\left(B_n\right)$ 中的任意两个顶点关于集合$W_f$ 有不同的度量表示，所以$W_f$ 是图$B_n$ 的解析集。从$W_f$ 中任意去掉一个顶点可得$W_f$ 的四个子集，分别是$W_1=\left\{a_1,a_2,a_{\lfloor \frac{n}{2}\rfloor +1}\right\}$ ，$W_2=\left\{a_1,a_2,a_{\lfloor \frac{n}{2}\rfloor +2}\right\}$ ，$W_3=\left\{a_1,a_{\lfloor \frac{n}{2}\rfloor +1},a_{\lfloor \frac{n}{2}\rfloor +2}\right\}$ 和$W_4=\left\{a_2,a_{\lfloor \frac{n}{2}\rfloor +1},a_{\lfloor \frac{n}{2}\rfloor +2}\right\}$ 。由上面的(1)~(5)可以看出，$V\left(B_n\right)$ 中的任意两个顶点关于$W_i\left(1\le i\le 4\right)$ 有不同的度量表示，$W_i\left(1\le i\le 4\right)$ 是$B_n$ 的解析集。由容错解析集的定义可知$W_f$ 是$B_n$ 的容错解析集。因此，${\dim }_f\left(B_n\right)\le 4$ 。由引理1.1和1.2，可得${\dim }_f\left(B_n\right)\ge 4$ 。综上，当$n\ge 6$ 时，${\dim }_f\left(B_n\right)=4$ 。

3. 凸多胞体图$C_n$ 的容错度量维数

首先介绍凸多胞体图$C_n$ ，凸多胞体图$C_n$ 有$5n$ 个点和$10n$ 条边，如图2所示。图$C_n$ 的顶点集和边集定义如下：

$V\left(C_n\right)=\{a_i,b_i,c_i,d_i,f_i:1\le i\le n\};$

$\begin{array}{c}E\left(C_n\right)=\{a_i{a}_{i+1},b_i{b}_{i+1},d_i{d}_{i+1},f_i{f}_{i+1}:1\le i\le n\}\\ \cup \{a_i{b}_i,b_i{c}_i,c_i{d}_i,d_i{f}_i,b_{i+1}{c}_i,d_{i+1}{f}_i:1\le i\le n\}.\end{array}$

Figure 2. The convex polytope graph C_n

图2. 凸多胞体图C_n

引理2.1 [13] 当$n\ge 6$ 时，凸多胞体图$C_n$ 的度量维数$\dim \left(C_n\right)=3$ 。

定理2.1 当$n\ge 6$ 时，凸多胞体图$C_n$ 的容错度量维数${\dim }_f\left(C_n\right)=4$ 。

证明：当$n\ge 6$ 时，设$W_f=\left\{a_1,a_2,a_{\lfloor \frac{n}{2}\rfloor +1},a_{\lceil \frac{n}{2}\rceil +2}\right\}$ 。下面证明$W_f$ 是凸多胞体图$C_n$ 的一个容错度量解析集。$C_n$ 中的每个顶点关于$W_f$ 的度量表示如下：

$r\left(a_i|W_f\right)=\{\begin{array}{ll}\left(0,1,\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil -1\right),\hfill & i=1;\hfill \\ \left(i-1,i-2,\lfloor \frac{n}{2}\rfloor -i+1,\lfloor \frac{n}{2}\rfloor -i+2\right),\hfill & 2\le i\le \lfloor \frac{n}{2}\rfloor +1;\hfill \\ \left(\lceil \frac{n}{2}\rceil -1,\lfloor \frac{n}{2}\rfloor ,1,0\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +2;\hfill \\ \left(n-i+1,n-i+2,i-\lfloor \frac{n}{2}\rfloor -1,i-\lfloor \frac{n}{2}\rfloor -2\right),\hfill & \lfloor \frac{n}{2}\rfloor +3\le i\le n;\hfill \end{array}$ (6)

$r\left(b_i|W_f\right)=\{\begin{array}{ll}\left(1,2,\lfloor \frac{n}{2}\rfloor +1,\lceil \frac{n}{2}\rceil \right),\hfill & i=1;\hfill \\ \left(i,i-1,\lfloor \frac{n}{2}\rfloor -i+2,\lfloor \frac{n}{2}\rfloor -i+3\right),\hfill & 2\le i\le \lfloor \frac{n}{2}\rfloor +1;\hfill \\ \left(\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor +1,2,1\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +2;\hfill \\ \left(n-i+2,n-i+3,i-\lfloor \frac{n}{2}\rfloor ,i-\lfloor \frac{n}{2}\rfloor -1\right),\hfill & \lfloor \frac{n}{2}\rfloor +3\le i\le n;\hfill \end{array}$ (7)

$r\left(c_i|W_f\right)=\{\begin{array}{ll}\left(2,2,\lfloor \frac{n}{2}\rfloor +1,\lceil \frac{n}{2}\rceil +1\right),\hfill & i=1;\hfill \\ \left(i+1,i,\lfloor \frac{n}{2}\rfloor -i+2,\lfloor \frac{n}{2}\rfloor -i+3\right),\hfill & 2\le i\le \lfloor \frac{n}{2}\rfloor ;\hfill \\ \left(\lceil \frac{n}{2}\rceil +1,\lfloor \frac{n}{2}\rfloor +1,2,2\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +1;\hfill \\ \left(n-i+2,n-i+3,i-\lfloor \frac{n}{2}\rfloor +1,i-\lfloor \frac{n}{2}\rfloor \right),\hfill & \lfloor \frac{n}{2}\rfloor +2\le i\le n;\hfill \end{array}$ (8)

$r\left(d_i|W_f\right)=\{\begin{array}{ll}\left(3,3,\lfloor \frac{n}{2}\rfloor +2,\lceil \frac{n}{2}\rceil +2\right),\hfill & i=1;\hfill \\ \left(i+2,i+1,\lfloor \frac{n}{2}\rfloor -i+3,\lfloor \frac{n}{2}\rfloor -i+4\right),\hfill & 2\le i\le \lfloor \frac{n}{2}\rfloor ;\hfill \\ \left(\lceil \frac{n}{2}\rceil +2,\lfloor \frac{n}{2}\rfloor +2,3,3\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +1;\hfill \\ \left(n-i+3,n-i+4,i-\lfloor \frac{n}{2}\rfloor +2,i-\lfloor \frac{n}{2}\rfloor +1\right),\hfill & \lfloor \frac{n}{2}\rfloor +2\le i\le n;\hfill \end{array}$ (9)

$r\left(f_i|W_f\right)=\{\begin{array}{ll}\left(4,4,\lfloor \frac{n}{2}\rfloor -i+4,\lceil \frac{n}{2}\rceil +2\right),\hfill & i=1;\hfill \\ \left(4,4,\lfloor \frac{n}{2}\rfloor -i+4,\lfloor \frac{n}{2}\rfloor +3\right),\hfill & i=2;\hfill \\ \left(i+2,i+1,\lfloor \frac{n}{2}\rfloor -i+4,\lfloor \frac{n}{2}\rfloor -i+5\right),\hfill & 3\le i\le \lfloor \frac{n}{2}\rfloor ;\hfill \\ \left(\lfloor \frac{n}{2}\rfloor +3,i+1,4,4\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +1;\hfill \\ \left(\lceil \frac{n}{2}\rceil +2,i+1,4,4\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +2;\hfill \\ \left(n-i+4,n-i+5,i-\lfloor \frac{n}{2}\rfloor +2,i-\lfloor \frac{n}{2}\rfloor +1\right),\hfill & \lfloor \frac{n}{2}\rfloor +3\le i\le n;\hfill \end{array}$ (10)

从度量表示(6)~(10)可以看出，$V\left(C_n\right)$ 中的任意两个顶点关于集合$W_f$ 有不同的度量表示，所以$W_f$ 是图$C_n$ 的解析集。从集合$W_f$ 中任意去掉一个顶点可得$W_f$ 的四个子集，分别是$W_1=\left\{a_1,a_2,a_{\lfloor \frac{n}{2}\rfloor +1}\right\}$ ，$W_2=\left\{a_1,a_2,a_{\lceil \frac{n}{2}\rceil +2}\right\}$ ，$W_3=\left\{a_1,a_{\lfloor \frac{n}{2}\rfloor +1},a_{\lceil \frac{n}{2}\rceil +2}\right\}$ 和$W_4=\left\{a_2,a_{\lfloor \frac{n}{2}\rfloor +1},a_{\lceil \frac{n}{2}\rceil +2}\right\}$ 。由上面的(6)~(10)可以看出，$V\left(C_n\right)$ 中的任意两个顶点关于$W_i\left(1\le i\le 4\right)$ 有不同的度量表示，$W_i\left(1\le i\le 4\right)$ 是$C_n$ 的解析集。由容错解析集的定义可知$W_f$ 是$C_n$ 的容错解析集。因此，${\dim }_f\left(C_n\right)\le 4$ 。由引理1.1和2.1，可得${\dim }_f\left(C_n\right)\ge 4$ 。综上，当$n\ge 6$ 时，${\dim }_f\left(C_n\right)=4$ 。

4. 凸多胞体图$E_n$ 的容错度量维数

首先给出凸多胞体图$E_n$ 的定义，凸多胞体图$E_n$ 有$5n$ 个点和$11n$ 条边，如图3所示。图$E_n$ 的顶点集和边集定义如下：

$V\left(E_n\right)=\{a_i,b_i,c_i,d_i,f_i:1\le i\le n\};$

$\begin{array}{c}E\left(E_n\right)=\{a_i{a}_{i+1},b_i{b}_{i+1},d_i{d}_{i+1},f_i{f}_{i+1}:1\le i\le n\}\\ \cup \{a_i{b}_i,b_i{c}_i,c_i{d}_i,d_i{f}_i,a_{i+1}{b}_i,b_{i+1}{c}_i,d_{i+1}{f}_i:1\le i\le n\}.\end{array}$

Figure 3. The convex polytope graph E_n

图3. 凸多胞体图E_n

引理3.1 [13] 当$n\ge 6$ 时，凸多胞体图$E_n$ 的度量维数$\dim \left(E_n\right)=3$ 。

定理3.1 当$n\ge 6$ 时，凸多胞体图$E_n$ 的容错度量维数${\dim }_f\left(E_n\right)=4$ 。

证明：(1) 当$6\le n\le 8$ 时，容易计算，凸多胞体图$E_n$ 的容错度量基和容错度量维数如表1所示。

Table 1. The fault-tolerant metric basis and the fault-tolerant metric dimension of E_n where 6 ≤ n ≤ 8

表1. 6 ≤ n ≤ 8时图E_n的容错度量基和容错度量维数

$n$	$E_n$ 的容错度量基	${\dim }_f\left(E_n\right)$
6	$\left\{a_1,a_3,f_1,f_6\right\}$	4
7	$\left\{a_1,a_2,a_4,a_6\right\}$	4
8	$\left\{a_1,a_3,a_5,a_7\right\}$	4

(2) 当$n=2s+1\left(s\ge 4\right)$ 时，设$W_f=\left\{a_1,a_2,a_{\lfloor \frac{n}{2}\rfloor +1},a_{\lfloor \frac{n}{2}\rfloor +3}\right\}$ 。下面证明$W_f$ 是凸多胞体图$E_n$ 的一个容错度量解析集。$E_n$ 中的每个顶点关于$W_f$ 的度量表示如下：

$r\left(a_i|W_f\right)=\{\begin{array}{ll}\left(i-1,2-i,\lfloor \frac{n}{2}\rfloor -i+1,\lfloor \frac{n}{2}\rfloor +i-2\right),\hfill & 1\le i\le 2;\hfill \\ \left(i-1,i-2,\lfloor \frac{n}{2}\rfloor -i+1,\lfloor \frac{n}{2}\rfloor -i+3\right),\hfill & 3\le i\le \lfloor \frac{n}{2}\rfloor +1;\hfill \\ \left(n-i+1,\lfloor \frac{n}{2}\rfloor ,i-\lfloor \frac{n}{2}\rfloor -1,\lfloor \frac{n}{2}\rfloor -i+3\right),\hfill & \lfloor \frac{n}{2}\rfloor +2\le i\le \lfloor \frac{n}{2}\rfloor +3;\hfill \\ \left(n-i+1,n-i+2,i-\lfloor \frac{n}{2}\rfloor -1,i-\lfloor \frac{n}{2}\rfloor -3\right),\hfill & \lfloor \frac{n}{2}\rfloor +4\le i\le n;\hfill \end{array}$ (11)

$r\left(b_i|W_f\right)=\{\begin{array}{ll}\left(i,1,\lfloor \frac{n}{2}\rfloor -i+1,\lfloor \frac{n}{2}\rfloor +i-1\right),\hfill & 1\le i\le 2;\hfill \\ \left(i,i-1,\lfloor \frac{n}{2}\rfloor -i+1,\lfloor \frac{n}{2}\rfloor -i+3\right),\hfill & 3\le i\le \lfloor \frac{n}{2}\rfloor ;\hfill \\ \left(n-i+1,i-1,i-\lfloor \frac{n}{2}\rfloor ,\lfloor \frac{n}{2}\rfloor -i+3\right),\hfill & \lfloor \frac{n}{2}\rfloor +1\le i\le \lfloor \frac{n}{2}\rfloor +2;\hfill \\ \left(n-i+1,n-i+2,i-\lfloor \frac{n}{2}\rfloor ,i-\lfloor \frac{n}{2}\rfloor -2\right),\hfill & \lfloor \frac{n}{2}\rfloor +3\le i\le n;\hfill \end{array}$ (12)

$r\left(c_i|W_f\right)=\{\begin{array}{ll}\left(2,2,\lfloor \frac{n}{2}\rfloor ,\lfloor \frac{n}{2}\rfloor +1\right),\hfill & i=1;\hfill \\ \left(i+1,i,\lfloor \frac{n}{2}\rfloor -i+1,\lfloor \frac{n}{2}\rfloor -i+3\right),\hfill & 2\le i\le \lfloor \frac{n}{2}\rfloor -1;\hfill \\ \left(\lfloor \frac{n}{2}\rfloor +1,i,2,\lfloor \frac{n}{2}\rfloor -i+3\right),\hfill & \lfloor \frac{n}{2}\rfloor \le i\le \lfloor \frac{n}{2}\rfloor +1;\hfill \\ \left(\lfloor \frac{n}{2}\rfloor ,\lfloor \frac{n}{2}\rfloor +1,3,2\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +2;\hfill \\ \left(n-i+1,n-i+2,i-\lfloor \frac{n}{2}\rfloor +1,i-\lfloor \frac{n}{2}\rfloor -1\right),\hfill & \lfloor \frac{n}{2}\rfloor +3\le i\le n-1;\hfill \\ \left(2,2,\lfloor \frac{n}{2}\rfloor +1,\lfloor \frac{n}{2}\rfloor \right),\hfill & i=n;\hfill \end{array}$ (13)

$r\left(d_i|W_f\right)=\{\begin{array}{ll}\left(3,3,\lfloor \frac{n}{2}\rfloor +1,\lfloor \frac{n}{2}\rfloor +2\right),\hfill & i=1;\hfill \\ \left(i+2,i+1,\lfloor \frac{n}{2}\rfloor -i+2,\lfloor \frac{n}{2}\rfloor -i+4\right),\hfill & 2\le i\le \lfloor \frac{n}{2}\rfloor -1;\hfill \\ \left(\lfloor \frac{n}{2}\rfloor +2,i+1,3,\lfloor \frac{n}{2}\rfloor -i+4\right),\hfill & \lfloor \frac{n}{2}\rfloor \le i\le \lfloor \frac{n}{2}\rfloor +1;\hfill \\ \left(\lfloor \frac{n}{2}\rfloor +1,\lfloor \frac{n}{2}\rfloor +2,4,3\right),\hfill & i=\lfloor \frac{n}{2}\rfloor +2;\hfill \\ \left(n-i+2,n-i+3,i-\lfloor \frac{n}{2}\rfloor +2,i-\lfloor \frac{n}{2}\rfloor \right),\hfill & \lfloor \frac{n}{2}\rfloor +3\le i\le n-1;\hfill \\ \left(3,3,\lfloor \frac{n}{2}\rfloor +2,\lfloor \frac{n}{2}\rfloor +1\right),\hfill & i=n;\hfill \end{array}$ (14)

$r\left(f_i|W_f\right)=\{\begin{array}{ll}\left(4,4,\lfloor \frac{n}{2}\rfloor +1,\lfloor \frac{n}{2}\rfloor +3\right),\hfill & i=1;\hfill \\ \left(i+3,i+2,\lfloor \frac{n}{2}\rfloor -i+2,\lfloor \frac{n}{2}\rfloor -i+4\right),\hfill & 2\le i\le \lfloor \frac{n}{2}\rfloor -2;\hfill \\ \left(i+3,i+2,4,\lfloor \frac{n}{2}\rfloor -i+4\right),\hfill & \lfloor \frac{n}{2}\rfloor -1\le i\le \lfloor \frac{n}{2}\rfloor ;\hfill \\ \left(n-i+2,n-i+3,i-\lfloor \frac{n}{2}\rfloor +3,4\right),\hfill & \lfloor \frac{n}{2}\rfloor +1\le i\le \lfloor \frac{n}{2}\rfloor +2;\hfill \\ \left(n-i+2,n-i+3,i-\lfloor \frac{n}{2}\rfloor +3,i-\lfloor \frac{n}{2}\rfloor +1\right),\hfill & \lfloor \frac{n}{2}\rfloor +3\le i\le n-2;\hfill \\ \left(4,4,n-\lfloor \frac{n}{2}\rfloor -i+2,i-\lfloor \frac{n}{2}\rfloor +1\right),\hfill & n-1\le i\le n;\hfill \end{array}$ (15)

从度量表示(11)~(15)可以看出，$V\left(E_n\right)$ 中的任意两个顶点关于集合$W_f$ 有不同的度量表示，所以$W_f$ 是图$E_n$ 的解析集。从集合$W_f$ 任意去掉一个顶点可得$W_f$ 的四个子集，分别是$W_1=\left\{a_1,a_2,a_{\lfloor \frac{n}{2}\rfloor +1}\right\}$ ，$W_2=\left\{a_1,a_2,a_{\lfloor \frac{n}{2}\rfloor +3}\right\}$ ，$W_3=\left\{a_1,a_{\lfloor \frac{n}{2}\rfloor +1},a_{\lfloor \frac{n}{2}\rfloor +3}\right\}$ 和$W_4=\left\{a_2,a_{\lfloor \frac{n}{2}\rfloor +1},a_{\lfloor \frac{n}{2}\rfloor +3}\right\}$ 。由上面的(11)~(15)可以看出$V\left(E_n\right)$ 中的任意两个顶点关于$W_i\left(1\le i\le 4\right)$ 有不同的度量表示。$W_i\left(1\le i\le 4\right)$ 是$E_n$ 的解析集。由容错解析集的定义可知$W_f$ 是$E_n$ 的容错解析集。因此，${\dim }_f\left(E_n\right)\le 4$ 。结合引理1.1和3.1，可得${\dim }_f\left(E_n\right)\ge 4$ 。综上，当$n=2s+1$ $\left(s\ge 4\right)$ 时，${\dim }_f\left(E_n\right)=4$ 。

(3) 当$n=2s$ $\left(s>4\right)$ 时，设$W_f=\left\{a_1,a_3,a_{\lfloor \frac{n}{2}\rfloor +1},a_{\lfloor \frac{n}{2}\rfloor +3}\right\}$ 。下面证明$W_f$ 是凸多胞体图$E_n$ 的一个容错度量解析集。$E_n$ 中的每个顶点关于$W_f$ 的度量表示如下：

$r\left(a_i|W_f\right)=\{\begin{array}{ll}\left(i-1,3-i,\frac{n}{2}-i+1,\frac{n}{2}+i-3\right),\hfill & 1\le i\le 3;\hfill \\ \left(i-1,i-3,\frac{n}{2}-i+1,\frac{n}{2}-i+3\right),\hfill & 4\le i\le \frac{n}{2}+1;\hfill \\ \left(n-i+1,i-\frac{n}{2}+3,i-\frac{n}{2}-1,\frac{n}{2}-i+3\right),\hfill & \frac{n}{2}+2\le i\le \frac{n}{2}+3;\hfill \\ \left(n-i+1,n-i+3,i-\frac{n}{2}-1,i-\frac{n}{2}-3\right),\hfill & \frac{n}{2}+4\le i\le n;\hfill \end{array}$ (16)

$r\left(b_i|W_f\right)=\{\begin{array}{ll}\left(i,3-i,\frac{n}{2}-i+1,\frac{n}{2}+i-2\right),\hfill & 1\le i\le 2;\hfill \\ \left(i,i-2,\frac{n}{2}-i+1,\frac{n}{2}-i+3\right),\hfill & 3\le i\le \frac{n}{2};\hfill \\ \left(n-i+1,i-2,i-\frac{n}{2},\frac{n}{2}-i+3\right),\hfill & \frac{n}{2}+1\le i\le \frac{n}{2}+2;\hfill \\ \left(n-i+1,n-i+3,i-\frac{n}{2},i-\frac{n}{2}-2\right),\hfill & \frac{n}{2}+3\le i\le n;\hfill \end{array}$ (17)

$r\left(c_i|W_f\right)=\{\begin{array}{ll}\left(i+1,2,\frac{n}{2}-i+1,\frac{n}{2}+i-1\right),\hfill & 1\le i\le 2;\hfill \\ \left(i+1,i-1,\frac{n}{2}-i+1,\frac{n}{2}-i+3\right),\hfill & 3\le i\le \frac{n}{2}-1;\hfill \\ \left(n-i+1,i-1,2,\frac{n}{2}-i+3\right),\hfill & \frac{n}{2}\le i\le \frac{n}{2}+1;\hfill \\ \left(n-i+1,n-i+3,i-\frac{n}{2}+1,2\right),\hfill & \frac{n}{2}+2\le i\le \frac{n}{2}+3;\hfill \\ \left(n-i+1,n-i+3,i-\frac{n}{2}+1,i-\frac{n}{2}-1\right),\hfill & \frac{n}{2}+4\le i\le n-1;\hfill \\ \left(2,3,\frac{n}{2}+1,\frac{n}{2}-1\right),\hfill & i=n;\hfill \end{array}$ (18)

$r\left(d_i|W_f\right)=\{\begin{array}{ll}\left(i+2,3,\frac{n}{2}-i+2,\frac{n}{2}+i\right),\hfill & 1\le i\le 2;\hfill \\ \left(i+2,i,\frac{n}{2}-i+2,\frac{n}{2}-i+4\right),\hfill & 3\le i\le \frac{n}{2}-1;\hfill \\ \left(n+2-i,i,3,\frac{n}{2}-i+4\right),\hfill & \frac{n}{2}\le i\le \frac{n}{2}+1;\hfill \\ \left(n-i+2,n-i+4,i-\frac{n}{2}+2,3\right),\hfill & \frac{n}{2}+2\le i\le \frac{n}{2}+3;\hfill \\ \left(n-i+2,n-i+4,i-\frac{n}{2}+2,i-\frac{n}{2}\right),\hfill & \frac{n}{2}+4\le i\le n-1;\hfill \\ \left(3,4,\frac{n}{2}+2,\frac{n}{2}\right),\hfill & i=n;\hfill \end{array}$ (19)

$r\left(f_i|W_f\right)=\{\begin{array}{ll}\left(i+3,4,\frac{n}{2}-i+2,\frac{n}{2}+2\right),\hfill & 1\le i\le 2;\hfill \\ \left(i+3,i+1,\frac{n}{2}-i+2,\frac{n}{2}-i+4\right),\hfill & 3\le i\le \frac{n}{2}-2;\hfill \\ \left(\frac{n}{2}+2,i+1,4,\frac{n}{2}-i+4\right),\hfill & \frac{n}{2}-1\le i\le \frac{n}{2};\hfill \\ \left(n-i+2,\frac{n}{2}+2,i-\frac{n}{2}+3,4\right),\hfill & \frac{n}{2}+1\le i\le \frac{n}{2}+2;\hfill \\ \left(n-i+2,n-i+4,i-\frac{n}{2}+3,i-\frac{n}{2}+1\right),\hfill & \frac{n}{2}+3\le i\le n-2;\hfill \\ \left(4,n-i+4,\frac{n}{2}+2,i-\frac{n}{2}+1\right),\hfill & n-1\le i\le n;\hfill \end{array}$ (20)

从度量表示(16)~(20)可以看出，$V\left(E_n\right)$ 中的任意两个顶点关于集合$W_f$ 有不同的度量表示，所以$W_f$ 是图$E_n$ 的解析集。从集合$W_f$ 中去掉任意一个顶点可得$W_f$ 的四个子集，分别是$W_1=\left\{a_1,a_3,a_{\lfloor \frac{n}{2}\rfloor +1}\right\}$ ，$W_2=\left\{a_1,a_3,a_{\lfloor \frac{n}{2}\rfloor +3}\right\}$ ，$W_3=\left\{a_1,a_{\lfloor \frac{n}{2}\rfloor +1},a_{\lfloor \frac{n}{2}\rfloor +3}\right\}$ 和$W_4=\left\{a_3,a_{\lfloor \frac{n}{2}\rfloor +1},a_{\lfloor \frac{n}{2}\rfloor +3}\right\}$ 。由上面的(16)~(20)可以看出，$V\left(E_n\right)$ 中的任意两个顶点关于$W_i\left(1\le i\le 4\right)$ 有不同的度量表示。$W_i\left(1\le i\le 4\right)$ 是$E_n$ 的解析集。由容错解析集的定义可知$W_f$ 是$E_n$ 的容错解析集。因此，${\dim }_f\left(E_n\right)\le 4$ 。由引理1.1和3.1，可得${\dim }_f\left(E_n\right)\ge 4$ 。综上，当$n=2s$ $\left(s>4\right)$ 时，${\dim }_f\left(E_n\right)=4$ 。

定理成立。

5. 总结

本文通过构作凸多胞体图$B_n$ ，$C_n$ 和$E_n$ 的容错解析集，证明了当$n\ge 6$ 时凸多胞体图$B_n$ ，$C_n$ 和$E_n$ 的容错度量维数都为4。这些成果在图论和组合优化中具有一定的理论价值，并在组合优化、网络电信等方面有重要应用。由引理1.1可知，图的容错度量维数大于等于图的度量维数加1。本文证明了凸多胞体图$B_n$ ，$C_n$ 和$E_n$ $\left(n\ge 6\right)$ 的容错度量维数恰好等于其度量维数加1。一个自然的问题是：是否存在其它凸多胞体图，其容错度量维数大于其度量维数加1？这将是我们今后继续研究的问题。

基金项目

国家自然基金面上项目(11971146)，河北省创新能力培养资助项目(CXZZSS2024108)。

NOTES

^*第一作者。

^#通讯作者。