The distance-k dimension of graphs
The distance-k dimension of graphs
复制标题
图的距离k维
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Eunjeong Yi
中科院分区：
文献类型：
--
作者：
Jesse T. Geneson;Eunjeong Yi
图 G 的度量维度 dim(G) 是由机器人导航驱动的图参数，已被广泛研究。设 G 为顶点集 V (G) 的图，并设 d(x, y) 表示 G 中最短 x − y 路径的长度。对于正整数 k 且不同的 x, y ∈ V (G)，令 dk(x, y) = min{d(x, y), k + 1} 并令 Rk{x, y} = {z ∈ V (G) : dk(x, z) 6= dk(y,z)}。子集 S ⊆ V (G) 是 G 的距离 k 解析集，如果 |S ∩ Rk{x, y}|对于任何一对不同的 x, y ∈ V (G) ≥ 1，G 的距离 k 维度 dimk(G) 是 G 的所有距离 k 解析集上的最小基数。请注意，对于 G 的直径 d，如果 k ≥ d− 1，则 dimk(G) = dim(G)，并且 dim1(G) 是 Jannesari 和 Omoomi 在 2012 年引入的 G 的邻接维度。论文中，我们发起了图的距离k维的研究。我们获得距离 k 维的一些一般界限。对于所有 k ≥ 1，我们用 dimk(G) ∈ {1, n− 2, n− 1} 来表征 n 阶连通图 G。当 G 是循环或路径时，我们确定 dimk(G)。我们还研究了顶点或边删除对图的距离 k 维度的影响。
The metric dimension, dim(G), of a graph G is a graph parameter motivated by robot navigation that has been studied extensively. Let G be a graph with vertex set V (G), and let d(x, y) denote the length of a shortest x − y path in G. For a positive integer k and for distinct x, y ∈ V (G), let dk(x, y) = min{d(x, y), k + 1} and let Rk{x, y} = {z ∈ V (G) : dk(x, z) 6= dk(y, z)}. A subset S ⊆ V (G) is a distance-k resolving set of G if |S ∩ Rk{x, y}| ≥ 1 for any pair of distinct x, y ∈ V (G), and the distance-k dimension, dimk(G), of G is the minimum cardinality over all distance-k resolving sets of G. Note that, for the diameter d of G, dimk(G) = dim(G) if k ≥ d− 1, and dim1(G) is the adjacency dimension of G introduced by Jannesari and Omoomi in 2012. In this paper, we initiate the study of distance-k dimension of graphs. We obtain some general bounds for distance-k dimension. We characterize connected graphs G of order n with dimk(G) ∈ {1, n− 2, n− 1} for all k ≥ 1. We determine dimk(G) when G is a cycle or a path. We also examine the effect of vertex or edge deletion on the distance-k dimension of graphs.