Relationships Between the 2-Metric Dimension and the 2-Adjacency Dimension in the Lexicographic Product of Graphs
详细信息 查看全文
- 作者：A. Estrada-Moreno ; I. G. Yero ; J. A. Rodríguez-Velázquez
- 关键词：2 ; Metric dimension ; 2 ; Adjacency dimension ; Lexicographic product graphs
- 刊名：Graphs and Combinatorics
- 出版年：2016
- 出版时间：November 2016
- 年：2016
- 卷：32
- 期：6
- 页码：2367-2392
- 全文大小：1,029 KB
- 刊物类别：Mathematics and Statistics
- 刊物主题：Mathematics
Combinatorics
Engineering Design - 出版者：Springer Japan
- ISSN：1435-5914
- 卷排序：32
文摘
Given a connected simple graph \(G=(V(G),E(G))\), a set \(S\subseteq V(G)\) is said to be a 2-metric generator for G if and only if for any pair of different vertices \(u,v\in V(G)\), there exist at least two vertices \(w_1,w_2\in S\) such that \(d_G(u,w_i)\ne d_G(v,w_i)\), for every \(i\in \{1,2\}\), where \(d_G(x,y)\) is the length of a shortest path between x and y. The minimum cardinality of a 2-metric generator is the 2-metric dimension of G, denoted by \(\dim _2(G)\). The metric \(d_{G,2}: V(G)\times V(G)\longmapsto {\mathbb {N}}\cup \{0\}\) is defined as \(d_{G,2}(x,y)=\min \{d_G(x,y),2\}\). Now, a set \(S\subseteq V(G)\) is a 2-adjacency generator for G, if for every two vertices \(x,y\in V(G)\) there exist at least two vertices \(w_1,w_2\in S\), such that \(d_{G,2}(x,w_i)\ne d_{G,2}(y,w_i)\) for every \(i\in \{1,2\}\). The minimum cardinality of a 2-adjacency generator is the 2-adjacency dimension of G, denoted by \({\mathrm {adim}}_2(G)\). In this article, we obtain closed formulae for the 2-metric dimension of the lexicographic product \(G\circ H\) of two graphs G and H. Specifically, we show that \(\dim _2(G\circ H)=n\cdot {\mathrm {adim}}_2(H)+f(G,H),\) where \(f(G,H)\ge 0\), and determine all the possible values of f(G, H).