The effect of vertex or edge deletion on the metric dimension of graphs
The effect of vertex or edge deletion on the metric dimension of graphs
复制标题
顶点或边删除对图度量维度的影响
DOI：
10.4310/joc.2015.v6.n4.a2
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Eunjeong Yi
中科院分区：
文献类型：
--
作者：
Linda Eroh;P. Feit;Cong X. Kang;Eunjeong Yi
图 G 的度量维度 dim(G) 是一组顶点的最小基数，使得 G 的每个顶点都由其到所选顶点的距离向量唯一确定。令v和e分别表示图G的顶点和边。我们证明，对于任意整数k，存在图G使得dim(G − v) − dim(G) = k。对于任何图 G 的任意边 e，我们证明 dim(G − e) ≤ dim(G) + 2。我们还证明，对于属于相当一般的图类的 G，dim(G − e) ≥ dim(G) − 1 。此外，我们给出了一个例子，表明 dim(G)− dim(G− e) 可以任意大。
The metric dimension dim(G) of a graph G is the minimum cardinality of a set of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices. Let v and e respectively denote a vertex and an edge of a graph G. We show that, for any integer k, there exists a graph G such that dim(G − v) − dim(G) = k. For an arbitrary edge e of any graph G, we prove that dim(G − e) ≤ dim(G) + 2. We also prove that dim(G − e) ≥ dim(G) − 1 for G belonging to a rather general class of graphs. Moreover, we give an example showing that dim(G)− dim(G− e) can be arbitrarily large.