半折叠n-立方体图的度量维数的上界

An Upper Bound on the Metric Dimension of the Halved Folded n-Cube

摘要: 令图$G$ 是简单的无向连通图，图$G=\left(X,R\right)$ 的解析集$S\subseteq X$ 是指对于任意两个不同点$u,v\in X$ ，总存在$s_i\in S$ 使得$\partial \left(u,s_i\right)\ne \partial \left(v,s_i\right)$ 。图$G$ 的度量维数是所有解析集基数的最小值。本文针对直径$d\ge 3$ 的半折叠n-立方体图，在$n=4d+2$ 时构造了一个解析集，从而证明了$\frac{3}{8}{n}^2-\frac{5}{4}n$ 是该图度量维数的上界。最后，将所得上界与Babai的上界进行对比，发现所得上界在一定情况下更优。

Abstract: Let $G$ be a simple, undirected, connected graph. A resolving set $S\subseteq X$ for graph $G=\left(X,R\right)$ satisfies for any two vertices $u,v\in X$ , there exists $s_i\in S$ such that $\partial \left(u,s_i\right)\ne \partial \left(v,s_i\right)$ . The metric dimension of graph $G$ is the minimum cardinality of all resolving sets. In this paper, for the halved folded n-cube with diameter $d\ge 3$ , we construct a resolving set if $n=4d+2$ , and then prove $\frac{3}{8}{n}^2-\frac{5}{4}n$ is an upper bound on the metric dimension of the graph. Finally, compare the upper bound with Babai’s upper bounds, and obtain that the upper bound above is better in some conditions.

1. 引言

1975年，Slater [1]为了确定入侵者在网络中的位置，首次引入图的解析集和度量维数概念。下面将会介绍相关定义。本文总设图$G=\left(X,R\right)$ 是一个有限、无向、简单的连通图，其中集合$X$ 是顶点集，$R$ 是边集。图$G$ 中两个顶点$v,u$ 的距离指连接这两点最短路线的长度，记为$\partial \left(v,u\right)$ 。图$G$ 的直径是$G$ 中任意两点距离的最大值，简记为$d$ 。设非空集合$S=\left\{s_1,\cdots ,s_t\right\}\subseteq X$ ，如果对任意两个不同的顶点$u,v\in X$ ，总存在$s_i\in S$ 使得$\partial \left(u,s_i\right)\ne \partial \left(v,s_i\right)$ ，则称集合$S$ 是图$G$ 的解析集，也称$s_i$ (或$S$ )解析$u$ 和$v$ 。图$G$ 的度量维数是指图$G$ 所有解析集的基数的最小值，记作$\mu \left(G\right)$ 。

由于计算一般图的度量维数的精确值是NP-困难的[2]，所以前人的研究对象大多是某类具体图的度量维数的值或界。例如，Babai [3] [4]得到了强正则图和本原距离正则图的度量维数的上界；Chvátal [5]给出了Hamming图度量维数的上界；Cáceres等[6]确定了Hamming图$H_{2,k}$ 的度量维数的精确值；Bailey和Meagher [7]找到了Grassmann图$G_q\left(n,k\right)$ 在$k\ge 2$ 时的度量维数的一个上界；Bailey和Cameron [8]介绍了Johnson图和Kneser图的度量维数的一些结果；Bailey等[9]构造了Johnson图和Kneser图的多种解析集；冯敏和王恺顺[10]得到了双线性型图$H_q\left(n,d\right)$ 在$n\ge d\ge 2$ 时的度量维数的上界，这改进了Babai关于$H_q\left(n,d\right)$ 在$n\ge d\ge 4$ 时的度量维数的最一般上界；郭军等[11] [12]通过构造解析集分别得到了Johnson图、双奇图、双Grassmann图、扭Grassmann图、辛对偶极图和对称双线性型图的度量维数的上界。

除此之外，还有许多成果是关于n-立方体图及其相关图的度量维数。例如，Lindström [13]研究了n-立方体图的度量维数；Hertz [14]基于IP的交换算法指出了n-立方体图的度量维数的新上界；张跃忠等[15]对于折叠n-立方体图通过构建极小解析集的方式得到了该图的度量维数的上界；Kelenc等[16]研究了n-立方体图度量维数与边度量维数的关系，也研究了度量维数与混合度量维数的关系；关于折叠n-立方体图的半图(即半折叠n-立方体图)的度量维数，田毅等[17]刻画了$n=4d\left(d\ge 3\right)$ 时的上界，但对于其他情形下的度量维数还尚未研究。基于此，本文拟研究$n=4d+2\left(d\ge 3\right)$ 时，半折叠n-立方体图的度量维数的上界。

2. 半折叠n-立方体图

关于n-立方体图，Simó和Yebra [18]这样描述：每个顶点可以标记为由0和1组成的一个n-维列向量，两个顶点相邻当且仅当它们对应的分量上只有一个分量的数值是不同的。将两个顶点对应的列向量之间不同的分量个数定义为两向量之间的Hamming距离。则n-立方体图中两个顶点相邻当且仅当相应列向量之间的Hamming距离为1。显然，n-立方体图的顶点个数为$2^n$ ，直径为n。

令$n\ge 2$ 是偶数且令$\left[n\right]=\left\{1,\cdots ,n\right\}$ 。半折叠n-立方体图是一个拆分图，其顶点集为$V\left(G\right)=\left\{\tilde{u}|\tilde{u}=\left\{u,\overline{u}\right\},u\subseteq \left[n\right],\overline{u}\subseteq \left[n\right],u\cup \overline{u}=\left[n\right],u\cap \overline{u}=\varphi ,\left|u\right|\equiv 0\left(\mathrm{mod}2\right)\right\}$ (其中$\varphi$ 表示空集)，两个顶点$\tilde{u},\tilde{w}$ 相邻当且仅当$\min \left\{\left|u\Delta w\right|,\left|u\Delta \overline{w}\right|\right\}=2$ ，其中符号$\Delta$ 表示对称差，即$u\Delta w=u\cup w-u\cap w=\left(u\backslash w\right)\cup \left(w\backslash u\right)$ 。显然，半折叠n-立方体图的直径$d=\lfloor \frac{n}{4}\rfloor$ 。由半折叠n-立方体图的定义知$\left|V\left(G\right)\right|=2^{n-2}$ ，且对于任意两个顶点$\tilde{u},\tilde{w}$ 有$\left|u\Delta w\right|+\left|u\Delta \overline{w}\right|=n$ 。因此，

$2\partial \left(\tilde{u},\tilde{w}\right)=\min \left\{\left|u\Delta w\right|,n-\left|u\Delta \overline{w}\right|\right\}$ (1)

为了方便，下文中用$G$ 表示半折叠n-立方体图，并给出下列两个注记：

注记1 顶点$\left\{u,\overline{u}\right\}$ 是满足$\left|u\right|\le \left|\overline{u}\right|$ 的有序对。令$X_r:=\left\{\tilde{u}=\left\{u,\overline{u}\right\}\in V\left(G\right)|\min \left\{\left|u\right|,\left|\overline{u}\right|\right\}=r\right\}$ ，则偶数$r$ 满足$0\le r\le \frac{n}{2}$ 且${\displaystyle \underset{r}{\cup }{X}_r}=V\left(G\right)$ 。

注记2 由注记1可知，顶点$\tilde{\varphi }=\left\{\varphi ,\left[n\right]\right\}\in X_0$ ，并且若$\tilde{u}\in X_k,\tilde{v}\in X_r$ 满足$k\ne r$ ，则有$\partial \left(\tilde{\varphi },\tilde{u}\right)\ne \partial \left(\tilde{\varphi },\tilde{v}\right)$ 。

3. 主要引理

本节将针对半折叠n-立方体图$G$ 证明两个重要引理。

引理1 设$\tilde{u}:=\left\{u,\overline{u}\right\}$ 和$\tilde{v}:=\left\{v,\overline{v}\right\}$ 是图$G$ 的不同顶点，且满足$\left|u\right|=\left|v\right|=k$ ，其中$k$ 是偶数且$2\le k\le \frac{n}{2}$ 。若$j\in u\Delta v$ ，则对于顶点$\tilde{x}:=\left\{x,\overline{x}\right\}\in V\left(G\right)$ (其中$x=\left\{i,j\right\}$ )，下列结论均成立：

(i) 如果$i\in u\cap v$ ，则$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ ；

(ii) 如果$i\in \overline{u}\cap \overline{v}$ ，且$n=4d$ ，或者$n=4d+2$ 且$k\le 2d-2$ ，则$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ ；

(iii) 如果$\left\{i,j\right\}\subseteq u\backslash v$ 或$v\backslash u$ ，且$n=4d+2$ 和$k=2d$ ，则$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。

证明 因为$j\in u\Delta v$ ，所以不失一般性总假设$j\in u\backslash v$ 。

(i) 由于$j\in u\backslash v$ 且$i\in u\cap v$ ，结合$\left|u\right|=\left|v\right|=k$ ，可得$\left|u\Delta x\right|=k-2$ 且$\left|v\Delta x\right|=k$ 。根据式(1)及$2\le k\le \frac{n}{2}$ ，得

$\partial \left(\tilde{u},\tilde{x}\right)=\min \left\{\frac{k-2}{2},\frac{n-\left(k-2\right)}{2}\right\}=\frac{k-2}{2}$

且

$\partial \left(\tilde{v},\tilde{x}\right)=\min \left\{\frac{k}{2},\frac{n-k}{2}\right\}=\frac{k}{2}$

因此，结论成立。

(ii) 由于$j\in u\backslash v$ 且$i\in \overline{u}\cap \overline{v}$ ，可得$\left|u\Delta x\right|=\left|u\right|=k$ 且$\left|v\Delta x\right|=\left|v\right|+2=k+2$ 。根据式(1)及$2\le k\le \frac{n}{2}$ ，得

$\partial \left(\tilde{u},\tilde{x}\right)=\min \left\{\frac{k}{2},\frac{n-k}{2}\right\}=\frac{k}{2}$

且

$\partial \left(\tilde{v},\tilde{x}\right)=\min \left\{\frac{k+2}{2},\frac{n-\left(k+2\right)}{2}\right\}$

显然，$\frac{k+2}{2}\ne \frac{k}{2}$ 。如果$n=4d$ ，因为$k$ 是偶数，容易得$\frac{n-\left(k+2\right)}{2}\ne \frac{k}{2}$ ；如果$n=4d+2$ 且$k\le 2d-2$ ，同样容易得$\frac{n-\left(k+2\right)}{2}\ne \frac{k}{2}$ 。综上，不论哪一种情况，都有$\frac{n-\left(k+2\right)}{2}\ne \frac{k}{2}$ 。因此，$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。

(iii) 由于$j\in u\backslash v$ 以及$\left\{i,j\right\}\subseteq u\backslash v$ 或$v\backslash u$ ，容易得出$i\in u\backslash v$ 。那么由$\left|u\right|=\left|v\right|=k=2d$ ，可得$\left|u\Delta x\right|=k-2=2d-2$ 且$\left|v\Delta x\right|=k+2=2d+2$ 。因为$n=4d+2$ ，根据式(1)可得

$\partial \left(\tilde{u},\tilde{x}\right)=\min \left\{\frac{2d-2}{2},\frac{4d+2-\left(2d-2\right)}{2}\right\}=d-1$

且

$\partial \left(\tilde{v},\tilde{x}\right)=\min \left\{\frac{2d+2}{2}，\frac{4d+2-\left(2d+2\right)}{2}\right\}=d$

因此，$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。

引理2 设图$G$ 是直径为$d$ 的半折叠n-立方体图，其中$n=4d+2\ge 14$ 。若

$\begin{array}{l}S=\left\{\left\{\varphi ,\left[n\right]\right\}\right\}\cup \left\{\left\{u,\overline{u}\right\}|u=\left\{i,j\right\},1\le i\le \frac{n}{2}-1,i+4\le j\le n\right\}\\ \cup \left\{\left\{u,\overline{u}\right\}|u=\left\{i,j\right\},i=\frac{n}{2},i+3\le j\le n\right\}\cup \left\{\left\{u,\overline{u}\right\}|u=\left\{i,j\right\},i=\frac{n}{2}+1,i+2\le j\le n\right\}\end{array}$

则下列结论成立：

(i) 对于任意$i\in \left[n\right]$ ，有$\left|\left\{j\in \left[n\right]|\left\{\left\{i,j\right\},\overline{\left\{i,j\right\}}\right\}\notin S\right\}\right|\le 2d+2$ ；

(ii) 对于任意两个不同的$i_1,i_2\in \left[n\right]$ ，有$\left|\left\{j\in \left[n\right]|\left\{\left\{i_1,j\right\},\overline{\left\{i_1,j\right\}}\right\}\notin S,\left\{\left\{i_2,j\right\},\overline{\left\{i_2,j\right\}}\right\}\notin S\right\}\right|\le 2d-2$ ；

(iii) 对于任意三个不同的$i_1,i_2,i_3\in \left[n\right]$ ，有$\left|\left\{j\in \left[n\right]|\left\{\left\{i_1,j\right\},\overline{\left\{i_1,j\right\}}\right\}\notin S,\left\{\left\{i_2,j\right\},\overline{\left\{i_2,j\right\}}\right\}\notin S,\left\{\left\{i_3,j\right\},\overline{\left\{i_3,j\right\}}\right\}\notin S\right\}\right|\le 2d-3$ 。

证明 对于任意$i\in \left[n\right]$ ，令$N_i=\left\{j\in \left[n\right]|\left\{\left\{i,j\right\},\overline{\left\{i,j\right\}}\right\}\notin S\right\}$ 。根据$S$ 的特点，得到表1。

Table 1. $N_i$ of $S$

表1. $S$ 的$N_i$

$i$	$N_i$	$\left|N_i\right|$
1	$\left\{2,3,4\right\}$	3
2	$\left\{1,3,4,5\right\}$	4
3	$\left\{1,2,4,5,6\right\}$	5
$4\le i\le \frac{n}{2}-1$	$\left\{i-3,i-2,i-1,i+1,i+2,i+3\right\}$	6
$i=\frac{n}{2}$	$\left\{i-3,i-2,i-1,i+1,i+2\right\}$	5
$i=\frac{n}{2}+1$	$\left\{i-3,i-2,i-1,i+1\right\}$	4
$i=\frac{n}{2}+2$	$\left\{i-3,i-2,i-1,i+1,\cdots ,n\right\}$	$\frac{n}{2}+1$
$\frac{n}{2}+3\le i\le n$	$\left\{\frac{n}{2}+2,\cdots ,n\right\}\backslash \left\{i\right\}$	$\frac{n}{2}-2$

(i) 由于$n=4d+2\ge 14$ ，有$\frac{n}{2}+1=2d+2>6$ 。由表1可知，对于任意$i\in \left[n\right]$ 有$\left|N_i\right|\le 2d+2$ ，结论成立。

(ii) 任取两个不同的$i_1,i_2\in \left[n\right]$ ，不妨设$i_1<i_2$ 。由表1可得：若$i_1=1$ ，则$\left|N_{i_1}\cap N_{i_2}\right|\le \left|N_{i_1}\right|=3$ ；若$i_1\in \left\{2,3\right\}$ ，则$\left|N_{i_1}\cap N_{i_2}\right|\le \left|N_{i_1}\right|-1\le 5-1=4$ ；若$i_1\in \left\{4,\cdots ,\frac{n}{2}+1\right\}$ ，则$|N_{i_1}\cap N_{i_2}|\le$ $\left|N_{i_1}\right|-2\le 6-2=4$ ；若$i_1\in \left\{\frac{n}{2}+2,\cdots ,n\right\}$ ，则$N_{i_1}\cap N_{i_2}=N_{i_2}\backslash \left\{i_1\right\}$ ，其中由于$i_1<i_2$ ，$i_2\in \left\{\frac{n}{2}+3,\cdots ,n\right\}$ ，因此$\left|N_{i_1}\cap N_{i_2}\right|=\left|N_{i_2}\right|-1=\frac{n}{2}-2-1=\frac{n}{2}-3=2d-2$ 。显然，当$d\ge 3$ 时，$2d-2\ge 4$ 。所以对于任意两个不同的$i_1,i_2\in \left[n\right]$ ，有$\left|N_{i_1}\cap N_{i_2}\right|\le 2d-2$ 。

(iii) 任取三个不同的$i_1,i_2,i_3\in \left[n\right]$ 。根据表1得，集合$N_{i_1}\cap N_{i_2}\cap N_{i_3}$ 是$N_{i_1}\cap N_{i_2}$ 或$N_{i_1}\cap N_{i_3}$ 或$N_{i_2}\cap N_{i_3}$ 的真子集。故由(ii)可得$\left|N_{i_1}\cap N_{i_2}\cap N_{i_3}\right|\le 2d-2-1=2d-3$ 。

4. 主要结论

已知$n=2,4,6,8$ 时半折叠n-立方体图的度量维数的精确值已经被确定(见文献[19] [20])；另外，文献[17]得到了$n=4d\left(d\ge 3\right)$ 时半折叠n-立方体图的度量维数的上界，本文主要讨论$n\equiv 2\left(\mathrm{mod}4\right)$ 且$n\ge 14$ 情况下半折叠n-立方体图的度量维数，得到下面结论。

定理1 设图$G$ 为半折叠n-立方体图。若$n\equiv 2\left(\mathrm{mod}4\right)$ 且$n\ge 14$ ，则$\mu \left(G\right)\le \frac{3}{8}{n}^2-\frac{5}{4}n$ 。

证明 构造集合

$\begin{array}{l}S=\left\{\left\{\varphi ,\left[n\right]\right\}\right\}\cup \left\{\left\{u,\overline{u}\right\}|u=\left\{i,j\right\},1\le i\le \frac{n}{2}-1,i+4\le j\le n\right\}\\ \cup \left\{\left\{u,\overline{u}\right\}|u=\left\{i,j\right\},i=\frac{n}{2},i+3\le j\le n\right\}\cup \left\{\left\{u,\overline{u}\right\}|u=\left\{i,j\right\},i=\frac{n}{2}+1,i+2\le j\le n\right\}\end{array}$

容易计算$\left|S\right|=\frac{3}{8}{n}^2-\frac{5}{4}n$ 。要想证明$\mu \left(G\right)\le \frac{3}{8}{n}^2-\frac{5}{4}n$ ，只需证明集合$S$ 是图$G$ 的解析集。又因为$\left\{\varphi ,\left[n\right]\right\}\in S$ ，所以由注记2可知，只需证明对任意不同点$\tilde{u}=\left\{u,\overline{u}\right\},\tilde{v}=\left\{v,\overline{v}\right\}\in X_k$ (其中$k$ 是偶数且$2\le k\le 2d$ )，总存在$\tilde{x}=\left\{x,\overline{x}\right\}\in S$ 使得$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。由于$\left|u\right|=\left|v\right|=k$ 且$u\ne v$ ，故$\left|u\backslash v\right|=\left|v\backslash u\right|=k-\left|u\cap v\right|>0$ 。这意味着$\left|u\Delta v\right|=\left|u\backslash v\right|+\left|v\backslash u\right|\ge 2$ 且为偶数。下面考虑两种情形：$2\le k\le 2d-2$ 或$k=2d$ 。

情形1 $2\le k\le 2d-2$

因为$\left|u\cup v\right|\le \left|u\right|+\left|v\right|=2k\le 4d-4$ 且$n=4d+2$ ，所以$\left|\overline{u}\cap \overline{v}\right|\ge 6$ 。这意味着$\left(\overline{u}\cap \overline{v}\right)\cap \left\{6,\cdots ,n\right\}\ne \varphi$ 。下面考虑三种子情形：$1\in u\Delta v$ 、$u\Delta v\subseteq \left\{2,3,4\right\}$ 、$1\notin u\Delta v$ 且$\left(u\Delta v\right)\cap \left\{5,\cdots ,n\right\}\ne \varphi$ 。

(1) 若$1\in u\Delta v$ ，则令$x=\left\{1,i\right\}$ ，其中$i\in \left(\overline{u}\cap \overline{v}\right)\cap \left\{6,\cdots ,n\right\}$ 。显然，点$\tilde{x}=\left\{x,\overline{x}\right\}\in S$ 。又因为$2\le k\le 2d-2$ 且$n=4d+2$ ，所以由引理1 (ii)可知点$\tilde{x}$ 满足$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。

(2) 若$u\Delta v\subseteq \left\{2,3,4\right\}$ ，则根据$\left|u\Delta v\right|$ 为偶数可知$\left|u\Delta v\right|=2$ 。这意味着$\left(u\Delta v\right)\cap \left\{2,3\right\}\ne \varphi$ ，进而根据$\left|\overline{u}\cap \overline{v}\right|\ge 6$ 可知$\left(\overline{u}\cap \overline{v}\right)\cap \left\{7,\cdots ,n\right\}\ne \varphi$ 。此时令$x=\left\{i,j\right\}$ ，其中$i\in \overline{u}\cap \overline{v}\cap \left\{7,\cdots ,n\right\},j\in \left(u\Delta v\right)\cap \left\{2,3\right\}$ 。则$\tilde{x}=\left\{x,\overline{x}\right\}\in S$ 且由引理1 (ii)可知该点满足$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。

(3) 若$1\notin u\Delta v$ 且$\left(u\Delta v\right)\cap \left\{5,\cdots ,n\right\}\ne \varphi$ ，则令$x=\left\{1,i\right\}$ ，其中$i\in \left(u\Delta v\right)\cap \left\{5,\cdots ,n\right\}$ 。显然，点$\tilde{x}=\left\{x,\overline{x}\right\}\in S$ 。此时，$1\in u\cap v$ 或$1\in \overline{u}\cap \overline{v}$ 。若$1\in u\cap v$ ，则由引理1 (i)可知$\tilde{x}$ 满足$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ ；若$1\in \overline{u}\cap \overline{v}$ ，则由引理1 (ii)可知点$\tilde{x}$ 满足$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。

情形2 $k=2d$

因为$k\ge 6$ ，所以$d\ge 3$ 。由于$u\ne v$ 且$\left|u\right|=\left|v\right|=k=2d$ ，故$0\le \left|u\cap v\right|\le k-1=2d-1$ 。下面考虑六种子情形：$\left|u\cap v\right|=0$ 、$\left|u\cap v\right|=1$ 、$2\le \left|u\cap v\right|\le d$ 、$\left|u\cap v\right|=d+1$ 、$d+2\le \left|u\cap v\right|\le 2d-2$ 、$\left|u\cap v\right|=2d-1$ 。

(1) 若$\left|u\cap v\right|=0$ ，即$u\cap v=\varphi$ ，则令$w=\left\{\frac{n}{2}+2,\cdots ,n\right\}$ 。此时由$n=4d+2$ 可知$\left|w\right|=2d$ 。由于$\left|u\right|=\left|v\right|=2d$ 但$u\ne v$ ，故$u\ne w$ 或者$v\ne w$ 。不妨假设$u\ne w$ ，这意味着$u\cap \left\{1,\cdots ,\frac{n}{2}+1\right\}\ne \varphi$ 。令$i=\underset{p\in u}{\min }p,j=\underset{p\in u}{\max }p$ 。注意，由于$u\cap v=\varphi$ ，所以上述$i,j\in u\backslash v$ 。进一步地，由于$\left|u\right|=k\ge 6$ ，故$j\ge i+5$ ，其中$i\in \left\{1,\cdots ,\frac{n}{2}+1\right\}$ 。此时令$x=\left\{i,j\right\}$ 。则$\tilde{x}=\left\{x,\overline{x}\right\}\in S$ 且由引理1 (iii)可知该点满足$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。

(2) 若$\left|u\cap v\right|=1$ ，则不妨设$u\cap v=\left\{i\right\}$ 。由于$d\ge 3$ ，所以$\left|u\Delta v\right|=4d-2>2d+2$ 。根据引理2 (i)可知，存在$j\in u\Delta v$ 使得$x=\left\{i,j\right\}$ 满足$\tilde{x}=\left\{x,\overline{x}\right\}\in S$ 。则由引理1 (i)知该点$\tilde{x}=\left\{x,\overline{x}\right\}$ 满足$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。

(3) 若$2\le \left|u\cap v\right|\le d$ ，则任取两个不同数$i_1,i_2\in u\cap v$ 。因为$\left|u\right|=\left|v\right|=2d$ 且$\left|u\cap v\right|\le d$ ，所以$\left|u\Delta v\right|=\left|u\right|+\left|v\right|-2\left|u\cap v\right|\ge 4d-2d=2d>2d-2$ 。从而根据引理2 (ii)知，存在$i\in \left\{i_1,i_2\right\}$ 和$j\in u\Delta v$ 使得$\tilde{x}=\left\{x,\overline{x}\right\}\in S$ ，其中$x=\left\{i,j\right\}$ 。此时由引理1 (i)知该点$\tilde{x}=\{x,\overline{x}\}$ 满足$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。

(4) 若$\left|u\cap v\right|=d+1$ ，则由$d\ge 3$ 知$\left|u\cap v\right|\ge 4$ 。此时，任取三个不同数$i_1,i_2,i_3\in u\cap v$ 。根据$\left|u\Delta v\right|=2d-2>2d-3$ 和引理2 (iii)可知，存在$i\in \left\{i_1,i_2,i_3\right\},j\in u\Delta v$ 使得$\tilde{x}=\left\{x,\overline{x}\right\}\in S$ ，其中$x=\left\{i,j\right\}$ 。则由引理1 (i)知该点$\tilde{x}=\left\{x,\overline{x}\right\}$ 满足$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。

(5) 若$d+2\le \left|u\cap v\right|\le 2d-2$ ，则$d\ge 4$ 且$k\ge 8$ 。下面考虑集合$u\Delta v$ 。首先，由于$\left|u\cap v\right|\le 2d-2$ 且$\left|u\right|=\left|v\right|=k=2d$ ，可得$\left|u\Delta v\right|\ge 4$ ，这意味着$\left|u\backslash v\right|=\left|v\backslash u\right|\ge 2$ 。

① 若存在$i\in u\Delta v$ 使得$i\in \left\{1,\cdots ,\frac{n}{2}+1\right\}$ ，则不失一般性假设$i\in u\backslash v$ 。因为$\left|u\right|=k\ge 8$ ，所以存在$j\in u$ 使得$\left|j-i\right|\ge 4$ ，此时令$x=\left\{i,j\right\}$ ，则$\tilde{x}=\left\{x,\overline{x}\right\}\in S$ 。如果$j\in u\backslash v$ ，那么由引理1 (iii)可知该点$\tilde{x}$ 满足$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ ；如果$j\in u\cap v$ ，那么由引理1 (i)可知该点$\tilde{x}$ 满足$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。

② 若$u\Delta v\subseteq \left\{\frac{n}{2}+2,\cdots ,n\right\}$ ，则由$n=4d+2$ 可知$\left|u\Delta v\right|\le 2d$ 。然而根据$\left|v\backslash u\right|\ge 2$ 可知，$\left|u\cup v\right|=\left|u\right|+\left|v\backslash u\right|\ge 2d+2$ 。所以，存在$i\in u\cap v$ 使得$i\in \left\{1,\cdots ,\frac{n}{2}+1\right\}$ 。此时有断言：必存在$j\in u\Delta v$ 使得$\left|j-i\right|\ge 4$ 。事实上，如果所有$j\in u\Delta v$ 都有$\left|j-i\right|\le 3$ ，则根据$j\in \left\{\frac{n}{2}+2,\cdots ,n\right\}$ 和$i\in \left\{1,\cdots ,\frac{n}{2}+1\right\}$ 可知$j>i$ 。故$\left|j-i\right|=j-i\le 3$ 。这意味着$u\Delta v\subseteq \left\{i+1,i+2,i+3\right\}$ ，与$\left|u\Delta v\right|\ge 4$ 矛盾！因此，断言成立。此时令$x=\left\{i,j\right\}$ ，则$\tilde{x}=\left\{x,\overline{x}\right\}\in S$ ，且由引理1 (i)可知该点$\tilde{x}$ 满足$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。

(6) 若$\left|u\cap v\right|=2d-1$ ，则由$\left|u\right|=\left|v\right|=k=2d$ 可知$\left|u\backslash v\right|=\left|v\backslash u\right|=1$ 。不妨设$u\backslash v=\left\{i_1\right\},v\backslash u=\left\{i_2\right\}$ 。根据引理2 (ii)和$\left|u\cap v\right|=2d-1>2d-2$ 可知，存在$i\in \left\{i_1,i_2\right\}$ 和$j\in u\cap v$ ，使得$\tilde{x}=\left\{x,\overline{x}\right\}\in S$ ，其中$x=\left\{i,j\right\}$ 。由引理1 (i)可知该点$\tilde{x}$ 满足$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。

综上，对于任意不同的顶点$\tilde{u},\tilde{v}\in X_k$ ，$S$ 中总存在$\tilde{x}$ 使得$\partial \left(\tilde{u},\tilde{x}\right)\ne \partial \left(\tilde{v},\tilde{x}\right)$ 。因此$S$ 是图$G$ 的解析集。故$\mu \left(G\right)\le \left|S\right|=\frac{3}{8}{n}^2-\frac{5}{4}n$ ，结论得证。

文献[21]指出半折叠n-立方体图是本原的距离正则图，相关概念见文献[21]。关于本原的距离正则图的度量维数，Babai给出了下列结论。

引理3 [3] [4] 设图$\Gamma$ 是有$m$ 个点的本原的距离正则图，若图的价至少为3且直径$d\ge 2$ ，则有：

(i) $\mu \left(\Gamma \right)<4\sqrt{m}\log m$ ；

(ii) $\mu \left(\Gamma \right)<2d\frac{m}{m-M\left(\Gamma \right)}\log m$ ，其中$M\left(\Gamma \right)=\underset{0\le i\le d}{\max }\left|{\Gamma }_i\right|$ 。这里${\Gamma }_i$ 表示固定任何一个点之后与该点距离是$i$ 的点的集合。

下面针对半折叠n-立方体图，比较定理1中的上界和引理3中的两个上界。

首先，与引理3 (i)比较。已知半折叠n-立方体图的顶点数$m=2^{n-2}$ 且$n=4d+2\ge 14$ ，故$\log 2^{n-2}>1$ ，所以$4\sqrt{m}\log m=2^{\frac{n}{2}+1}\log 2^{n-2}>2^{\frac{n}{2}+1}$ 。令$g\left(x\right)=2^{\frac{x}{2}+1}-\frac{3}{8}{x}^2+\frac{5}{4}x$ 。容易发现，$g\left(x\right)$ 在$x\ge 14$ 时严格递增，并且$g\left(14\right)=200>0$ 。从而，$2^{\frac{n}{2}+1}>\frac{3}{8}{n}^2-\frac{5}{4}n$ 。这说明，定理1的上界比引理3 (i)的上界更优。

接下来与引理3 (ii)进行比较。由文献[21]知，半折叠n-立方体图的交叉阵列$a_i,b_i,c_i\left(0\le i\le d\right)$ 满足：

$b_i=\left(\frac{n}{2}-i\right)\left(n-2i-1\right),c_i=i\left(2i-1\right)\left(0\le i\le d-1\right),c_d=\{\begin{array}{l}d\left(2d-1\right),\frac{n}{2}\equiv 1\left(\mathrm{mod}2\right)\\ 2d\left(2d-1\right),\frac{n}{2}\equiv 0\left(\mathrm{mod}2\right)\end{array}$

在此基础上，结合$n=4d+2$ 得$b_{i-1}-c_i=-\left(8d+6\right)i+8d^2+14d+6\left(1\le i\le d\right)$ 。令$f\left(i\right):=-\left(8d+6\right)i+8d^2+14d+6$ 。容易证明函数$f\left(i\right)$ 在$1\le i\le d$ 上严格下降，所以$\min \left\{b_{i-1}-c_i\right\}=b_{d-1}-c_d=8d+6>0$ 。这意味着$b_{i-1}>c_i$ $\left(1\le i\le d\right)$ 。由文献[21]可知， $\left|G_i\right|=\frac{b_0{b}_1\cdots b_{i-1}}{c_1{c}_2\cdots c_i}\left(1\le i\le d\right)$ ，且$\left|G0\right|=1$ 。因此，

$M\left(G\right)=\underset{1\le i\le d}{\max }\frac{b_0{b}_1\cdots b_{i-1}}{c_1{c}_2\cdots c_i}=\frac{b_0{b}_1\cdots b_{d-1}}{c_1{c}_2\cdots c_d}=\frac{\left(2d\right)!\left(4d+1\right)!!}{d!\left(d+1\right)!{\left(\left(2d-1\right)!!\right)}^2}$

其中$!$ 和$!!$ 分别表示阶乘和双阶乘。此时，引理3 (ii)的上界为

$2d\frac{2^{4d}\log 2^{4d}}{2^{4d}-\frac{\left(2d\right)!\left(4d+1\right)!!}{d!\left(d+1\right)!{\left(\left(2d-1\right)!!\right)}^2}}$

利用Mathematica软件比较了该上界和定理1中的上界，发现在$d=3,4,5$ 时，定理1的上界更优。

5. 小结

本文通过构造解析集的方法，讨论了$n=4d+2\left(d\ge 3\right)$ 时半折叠n-立方体图的度量维数的上界，虽然没有刻画出度量维数的精确值，但是通过和Babai所得的上界进行比较，发现所得上界在一些情况下是更优的。后续将在此基础上，进一步刻画更好的上界或其精确值。

基金项目

河北省教育厅科学研究项目(QN2025114)；河北省金融科技应用重点实验室课题(2024004)；河北金融学院育苗课题(YMZX202313)。

NOTES

^*通讯作者。