The $k$-metric dimension of the lexicographic product of graphs

• DOI: 10.48550/arxiv.1410.7287
• Publication Date: 2014-01-01
• Authors: Alejandro Estrada...; Ismael G. Yero; Juan A. Rodríguez...
• Keywords: Metric Dimension; Lexicographical order; Cardinality (data modeling); Adjacency list

Given a simple and connected graph $G=(V,E)$, positive integer $k$, set $S\subseteq V$ is said to be $k$-metric generator for $G$, if any pair of different vertices $u,v\in V$, there exist at least $k$ $w_1,w_2,\ldots,w_k\in S$ such that $d_G(u,w_i)\ne d_G(v,w_i)$, every $i\in \{1,\ldots,k\}$, where $d_G(x,y)$ denotes the distance between $x$ $y$. The minimum cardinality dimension $G$. A $k$-adjacency $G$ two $x,y\in V(G)$ satisfy $|((N_G(x)\triangledown N_G(y))\cup\{x,y\})\cap S|\ge k$, $N_G(x)\triangledown N_G(y)$ symmetric difference neighborhoods In this article we obtain tight bounds closed formulae lexicographic product graphs in terms factor graphs.