The k-metric dimension of the lexicographic product of graphs
Review articleOpen access
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

References (0)

Cited By (0)

No reference data.
No citation data.
Advertisement
Join Copernicus Academic and get access to over 12 million papers authored by 7+ million academics.
Join for free!