一类半折叠n-立方体图的度量维数

The Metric Dimension of a Class of Halved Folded n-Cube

摘要: 图的度量维数在通信网络中的有效寻址系统、标尺模型和雷达脉冲码等方面都有重要的应用。本文关于n = 4d (d ≥ 3)的半折叠n-立方体图，通过构造解析集的方式证明了n − 1是该类图的度量维数的上界。最后，将该上界与Babai的上界进行了对比，发现本文所得上界更优。

Abstract: The metric dimension of the graph has important applications in the effective addressing system, scale model and radar pulse code in communication networks. In this paper, for the halved folded n-cube with n = 4d (d ≥ 3), we prove that n − 1 is an upper bound on the metric dimension of this graph by constructing a resolving set. Finally, we compare the upper bound with Babai’s upper bounds, and obtain that the upper bound above is better.

1. 引言

1975年，P. J. 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$ 。如果解析集$S$ 的任何一个真子集都不再是$G$ 的解析集，则称解析集$S$ 为极小的。图$G$ 的度量维数是指图$G$ 的所有解析集的基数的最小值，记作$\mu \left(G\right)$ 。

由于计算一般图的度量维数的精确值是NP-困难的[2]，所以前人的研究对象大多是某类具体图的度量维数的值或界。例如，L. Babai [3] [4]得到了强正则图和本原距离正则图的度量维数的上界；V. Chvátal [5]给出了Hamming图度量维数的上界；J. Cáceres等[6]确定了Hamming图$H_{2,k}$ 的度量维数的精确值；R. F. Bailey和K. Meagher [7]找到了Grassmann图$G_q\left(n,k\right)$ 在$k\ge 2$ 时的度量维数的一个上界；R. F. Bailey和P. J. 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-立方体图及其相关图的度量维数。例如，B. Lindström [13]研究了n-立方体图的度量维数；A. Hertz [14]基于IP的交换算法指出了n-立方体图的度量维数的新上界；张跃忠等[15]对于折叠n-立方体图通过构建极小解析集的方式得到了该图的度量维数的上界。

目前，折叠n-立方体图的半图(即半折叠n-立方体图)的度量维数还尚未研究，本文拟研究这一问题，刻画该度量维数的上界，并将所得上界与已有上界进行比较。

2. 半折叠n-立方体图

关于n-立方体图，E. Simó和J. L. A. Yebra [16]这样描述：每个顶点可以标记为由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,\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-立方体图，并且规定$\left\{u,\overline{u}\right\}$ 是满足$\left|u\right|\le \left|\overline{u}\right|$ 的有序对。令$X_r=\left\{\tilde{u}=\left\{u,\overline{u}\right\}:\min \left\{\left|u\right|,\left|\overline{u}\right|\right\}=r\right\}$ ，则偶数$r$ 满足$0\le r\le \frac{n}{2}$ 且$\underset{r}{\cup }{X}_r=V\left(G\right)$ 。此时，若$\tilde{u}\in X_k,\tilde{v}\in X_r$ 满足$k\ne r$ ，则由(1)知$\partial \left(\tilde{\varphi },\tilde{u}\right)\ne \partial \left(\tilde{\varphi },\tilde{v}\right)$ 。

3. 主要结论

众所周知，$n=2,4,6$ 时半折叠n-立方体图为完全图。又因为文献[17] [18]已经分别得到了完全图和半折叠8-立方体图的度量维数，所以本文主要讨论$n=4d\left(d\ge 3\right)$ 的半折叠n-立方体图的度量维数，得到下面结论。

定理1 设图$G$ 为半折叠n-立方体图。若$n\equiv 0\left(\mathrm{mod}4\right)$ 且$n\ge 12$ ，则$\mu \left(G\right)\le n-1$ 。

证明 因为图$G$ 的直径$d=\lfloor \frac{n}{4}\rfloor$ 且$n\equiv 0\left(\mathrm{mod}4\right)$ ，所以$n=4d$ 。再由$n\ge 12$ 知$d\ge 3$ 。构造集合$S=\left\{\tilde{\varphi }\right\}\cup \left\{{\tilde{u}}_i:u_i=\left\{1,i\right\},2\le i\le n-1\right\}$

显然，$\left|S\right|=n-1$ 。下面只需证明$S$ 是图$G$ 的解析集即可得$\mu \left(G\right)\le n-1$ 。考虑到$\tilde{\varphi }\in S$ ，下面只需证明对于任意不同的顶点$\tilde{u},\tilde{v}\in X_k\left(2\le k\le \frac{n}{2}\right)$ ，$S$ 中总存在$\tilde{x}$ 使得$\partial \left(\tilde{x},\tilde{u}\right)\ne \partial \left(\tilde{x},\tilde{v}\right)$ 。

任取不同点$\tilde{u}=\left\{u,\overline{u}\right\},\tilde{v}=\left\{v,\overline{v}\right\}\in X_k$ ，显然$\left|u\right|=\left|v\right|=k$ 且$\left|u\Delta v\right|\ge 2$ 。下面讨论三种情形：$1\in u\cap v$ ，$1\in u\Delta v$ ，$1\in \overline{u}\cap \overline{v}$ 。

情形(i) $1\in u\cap v$

因为$1\in u\cap v$ 且$\left|u\Delta v\right|\ge 2$ ，所以存在$i\in \left\{2,\cdots ,n-1\right\}$ 使得$i\in u\Delta v$ ，不妨设$i\in u\backslash v$ 。令$x=\left\{1,i\right\}$ ，可知$\tilde{x}\in S$ 且由(1)知$\partial \left(\tilde{x},\tilde{u}\right)=\frac{k}{2}-1,\partial \left(\tilde{x},\tilde{v}\right)=\frac{k}{2}$。因此，$\partial \left(\tilde{x},\tilde{u}\right)\ne \partial \left(\tilde{x},\tilde{v}\right)$ 。

情形(ii) $1\in u\Delta v$

因为$1\in u\Delta v=\left(u\backslash v\right)\cup \left(v\backslash u\right)$ ，不失一般性假设$1\in u\backslash v$ 。下面分别讨论$k=2d$ 和$2\le k\le 2d-2$ 两种子情形。

若$k=2d$ ，则$\left|u\right|=\left|v\right|=2d$ 。又因为$\tilde{u},\tilde{v}\in X_k$ 是不同点，所以$u\cap v\ne \varphi$ 。若存在$i\in u\cap v$ 使得$i\in \left\{2,\cdots ,n-1\right\}$ ，则令$x=\left\{1,i\right\}$ ;若$u\cap v=\left\{n\right\}$ ，则$\left|\overline{u}\cap \overline{v}\right|=n-\left(k+k-1\right)=4d-2k+1=1$ ，这意味着存在$i\in \overline{u}\cap \overline{v}$ 使得$i\in \left\{2,\cdots ,n-1\right\}$ ，此时令$x=\left\{1,i\right\}$ 。易知上述两种$x$ 都满足$\tilde{x}\in S$ ，并且由(1)知$\partial \left(\tilde{x},\tilde{u}\right)$ 和$\partial \left(\tilde{x},\tilde{v}\right)$ 的取值一个是$d$ 一个是$d-1$ 。因此，$\partial \left(\tilde{x},\tilde{u}\right)\ne \partial \left(\tilde{x},\tilde{v}\right)$ 。

若$2\le k\le 2d-2$ ，则$\left|u\cup v\right|\le 2k\le 4d-4$ 。此时根据$n=4d$ 可知$\left|\overline{u}\cap \overline{v}\right|\ge 4$ 。所以存在$i\in \overline{u}\cap \overline{v}$ 使得$i\in \left\{2,\cdots ,n-1\right\}$ 。令$x=\left\{1,i\right\}$ ，可知$\tilde{x}\in S$ 且由(1)知$\partial \left(\tilde{x},\tilde{u}\right)=\frac{k}{2},\partial \left(\tilde{x},\tilde{v}\right)=\frac{k}{2}+1$。因此，$\partial \left(\tilde{x},\tilde{u}\right)\ne \partial \left(\tilde{x},\tilde{v}\right)$ 。

情形(iii) $1\in \overline{u}\cap \overline{v}$

因为$1\in \overline{u}\cap \overline{v}$ 且$\left|u\Delta v\right|\ge 2$ ，所以存在$i\in \left\{2,\cdots ,n-1\right\}$ 使得$i\in u\Delta v$ ，不妨设$i\in u\backslash v$ 。令$x=\left\{1,i\right\}$ ，则$\tilde{x}\in S$ 且由(1)知$\partial \left(\tilde{x},\tilde{u}\right)=\frac{k}{2},\partial \left(\tilde{x},\tilde{v}\right)=\min \left\{\frac{k+2}{2},\frac{n-\left(k+2\right)}{2}\right\}$。注意到，当$2d-2<k\le 2d$ (即$k=2d$ )时，由(1)知$\partial \left(\tilde{x},\tilde{u}\right)=d$ 且

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

当$2\le k\le 2d-2$ 时，由(1)知$\partial \left(\tilde{x},\tilde{v}\right)=\min \left\{\frac{k+2}{2},\frac{n-\left(k+2\right)}{2}\right\}=\frac{k}{2}+1$ 且$\partial \left(\tilde{x},\tilde{u}\right)=\frac{k}{2}$ 。因此，$\partial \left(\tilde{x},\tilde{u}\right)\ne \partial \left(\tilde{x},\tilde{v}\right)$ 。

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

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

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

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

2) $\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中的上界和引理1中的上界。已知半折叠n-立方体图的顶点数$m=2^{n-2}$ 且$n=4d\left(d\ge 3\right)$ ，所以

$4\sqrt{m}\log m=2^{\frac{n}{2}+1}\log 2^{n-2}>2^{\frac{n}{2}+1}=2^{2d+1}$

且

$2d\frac{m}{m-M\left(\Gamma \right)}\log m=2d\frac{2^{n-2}}{2^{n-2}-M\left(\Gamma \right)}\log 2^{n-2}>2d\log 2^{4d-2}$

令$f\left(x\right)=2^{2x+1}-4x+1$ ，$h\left(x\right)=2x\log 2^{4x-2}-4x+1$ 。容易发现，$f\left(x\right)$ 和$h\left(x\right)$ 在$x\ge 3$ 时严格递增。又因为$f\left(3\right)=117>0$ 且$h\left(3\right)=60\log 2-11>0$ ，所以$2^{2d+1}>4d-1=n-1$ 且$2d\log 2^{4d-2}>4d-1=n-1$ 。这说明定理1的上界比Babai所得的上界更优。

关于图的度量维数的下界，有下列引理：

引理2 [20]设图$\Gamma$ 是$m$ 个点直径为$d$ 的图。则$\mu \left(\Gamma \right)$ 满足$m\le {\left(\lfloor \frac{2d}{3}\rfloor +1\right)}^{\mu \left(\Gamma \right)}+\mu \left(\Gamma \right){\displaystyle \sum _{i=1}^{\lceil \frac{d}{3}\rceil }{\left(2i-1\right)}^{\mu \left(\Gamma \right)-1}}$ 。

已知半折叠4-立方体图是完全图$K_4$ ，其度量维数的精确值为3 [17]；半折叠8-立方体图是强正则图，其度量维数的精确值为7 [18]。这说明$n=4d$ 且$d=1,2$ 时，$\mu \left(G\right)=n-1$ 。在此基础上，结合定理1和引理2可得下面结论。

定理2 设图$G$ 为有$m$ 个点的半折叠n-立方体图。若$n\equiv 0\left(\mathrm{mod}4\right)$ ，则$\mu \left(G\right)$ 满足$\mu \left(G\right)\le n-1$ 且$m\le {\left(\lfloor \frac{2d}{3}\rfloor +1\right)}^{\mu \left(\Gamma \right)}+\mu \left(\Gamma \right){\displaystyle \sum _{i=1}^{\lceil \frac{d}{3}\rceil }{\left(2i-1\right)}^{\mu \left(\Gamma \right)-1}}$ ，其中$d$ 为图$G$ 的直径。

根据定理2，在半折叠n-立方体图满足$n\equiv 0\left(\mathrm{mod}4\right)$ 时，针对n的具体值，可以计算出其度量维数的上下界。比如，在$n=12$ 时，有$7\le \mu \left(G\right)\le 11$ ，这在一定程度上推进了其度量维数精确值的刻画进程。

4. 小结

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

致 谢

衷心感谢审稿专家提出的宝贵建设性意见，这些意见提升了本文的质量。同时感谢编辑部和审稿人在评审过程中展现的专业严谨。

基金项目

本文的资助信息如下：河北省教育厅科学研究项目(QN2025114)，河北省金融科技应用重点实验室课题(2024004)，河北金融学院育苗课题(YMZX202313)。

NOTES

^*通讯作者。