The kk-metric dimension of the lexicographic product of graphs

preprint2015arXivOpen access

Abstract

Given a simple and connected graph G=(V,E)G=(V,E), and a positive integer kk, a set S⊆VS\subseteq V is said to be a kk-metric generator for GG, if for any pair of different vertices u,v∈Vu,v\in V, there exist at least kk vertices w1,w2,…,wk∈Sw_1,w_2,\ldots,w_k\in S such that dG(u,wi)≠dG(v,wi)d_G(u,w_i)\ne d_G(v,w_i), for every i∈{1,…,k}i\in \{1,\ldots,k\}, where dG(x,y)d_G(x,y) denotes the distance between xx and yy. The minimum cardinality of a kk-metric generator is the kk-metric dimension of GG. A set S⊆VS\subseteq V is a kk-adjacency generator for GG if any two different vertices x,y∈V(G)x,y\in V(G) satisfy ∣((NG(x)▽NG(y))∪{x,y})∩S∣≥k|((N_G(x)\triangledown N_G(y))\cup\{x,y\})\cap S|\ge k, where NG(x)▽NG(y)N_G(x)\triangledown N_G(y) is the symmetric difference of the neighborhoods of xx and yy. The minimum cardinality of any kk-adjacency generator is the kk-adjacency dimension of GG. In this article we obtain tight bounds and closed formulae for the kk-metric dimension of the lexicographic product of graphs in terms of the kk-adjacency dimension of the factor graphs.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.