半折叠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.