An Upper Bound on the Metric Dimension of the Halved Folded <i>n</i>-Cube

令图 G 是简单的无向连通图，图 G=( X,R ) 的解析集 S⊆X 是指对于任意两个不同点 u,v∈X ，总存在 s i ∈S 使得 ∂( u, s i )≠∂( v, s i ) 。图 G 的度量维数是所有解析集基数的最小值。本文针对直径 d≥3 的半折叠n-立方体图，在 n=4d+2 时构造了一个解析集，从而证明了 3 8 n 2 − 5 4 n 是该图度量维数的上界。最后，将所得上界与Babai的上界进行对比，发现所得上界在一定情况下更优。Let G be a simple, undirected, connected graph. A resolving set S⊆X for graph G=( X,R ) satisfies for any two vertices u,v∈X , there exists s i ∈S such that ∂( u, s i )≠∂( v, s i ) . 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≥3 , we construct a resolving set if n=4d+2 , and then prove 3 8 n 2 − 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.