The k-metric dimension of the lexicographic product of graphs

الأصل · EN

Given 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 w₁,w₂,,wₖ∈ S such that dG(u,wᵢ)≠ dG(v,wᵢ), 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.