On the (adjacency) metric dimension of corona and strong product graphs and their local variants: Combinatorial and computational results
On the (adjacency) metric dimension of corona and strong product graphs and their local variants: Combinatorial and computational results
复制标题
DOI：
10.1016/j.dam.2017.11.019
复制
发表时间：
2018-02-19
影响因子：
1.1
通讯作者：
Rodriguez-Velazquez, Juan A.
中科院分区：
文献类型：
--
作者：
Fernau, Henning;Rodriguez-Velazquez, Juan A.
度量维度是一个研究得很好的图参数。近年来，引入了邻接度量维数和局部度量维数。我们结合这些变量，引入了局部邻接度量维。我们证明了n阶图和非平凡图H的电晕积的（局部）度量维等于H的（局部）邻接度量维的n倍。这种强关系也使我们能够根据我们提供的（局部）邻接度量维的硬度结果，推断出计算（局部）度量维的计算硬度结果。我们还研究了图的强积的组合性质，并强调了不同类型的孪生在确定图的邻接度量维数方面所起的作用。(C) 2017 Elsevier B.V.版权所有
The metric dimension is quite a well-studied graph parameter. Recently, the adjacency metric dimension and the local metric dimension have been introduced. We combine these variants and introduce the local adjacency metric dimension. We show that the (local) metric dimension of the corona product of a graph of order n and some non-trivial graph H equals n times the (local) adjacency metric dimension of H. This strong relation also enables us to infer computational hardness results for computing the (local) metric dimension, based on according hardness results for (local) adjacency metric dimension that we also provide. We also study combinatorial properties of the strong product of graphs and emphasize the role of different types of twins play in determining in particular the adjacency metric dimension of a graph. (C) 2017 Elsevier B.V. All rights reserved.