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

Abstract

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

19 pages

References in corpus (2)

• The k-metric dimension of a graph
• The Simultaneous Metric Dimension of Graph Families

Cited by in corpus (1)

• On the adjacency dimension of graphs