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

Review articleOpen access###### Alejandro Estrada-Moreno - No affiliation found

**2016/07/06**DOI: 10.1016/j.disc.2015.12.024

*Full-length article***Journal:**Discrete Mathematics

##### Abstract:

AbstractGiven a simple and connected graph G=(V,E), and a positive integer k, a set S⊆V is said to be a k-metric generator for G, if for any pair of different vertices u,v∈V, there exist at least k vertices w1,w2,…,wk∈S such that dG(u,wi)≠dG(v,wi), for every i∈{1,…,k}, where dG(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⊆V is a k-adjacency generator for G if any two different vertices x,y∈V(G) satisfy |((NG(x)▿NG(y))∪{x,y})∩S|≥k, where NG(x)▿NG(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.

Request full text