The doubly resolving number of the lexicographic product of graphs

Abstract

Two vertices u, v in a connected graph G are doubly resolved by vertices x, y of G if d(v, x) − d(u, x) ≠ d(v, y) − d(u, y). A set W of vertices of the graph G is a doubly resolving set for G if every two distinct vertices of G are doubly resolved by some two vertices of W. Doubly resolving number of a graph G, denoted by ψ(G), is the minimum cardinality of a doubly resolving set for G. The aim of this paper is to investigate doubly resolving sets in the lexicographic product graphs. It is proved that if H ∈/ {P3, P3} or G does not have any vertex of degree 1, then ψ(G[H]) = dim(G[H]). Also ψ(G[H]) is computed in other cases. © World Scientific Publishing Company.