Regresar

On the minimal doubly resolving sets of harary graph

Abstract:

Let G = (V, E) be a simple connected and undirected graph, where V and E represent the vertex and edge set, respectively. The vertices x and y doubly resolve the vertices u and v if the following condition is satisfied d(u, x) − d(u, y) ≠ d(v, x) − d(v, y). A subset D of vertex set V of G is said to be doubly resolving set of G if for every pair x′, y′ of distinct vertices of G, there exist two vertices x, y in D which doubly resolve the vertices x′, y′. A minimal doubly resolving set is a doubly resolving set which has minimum cardinality. The cardinality of minimal doubly resolving set is denoted by ψ(G). Let β(G) denotes the metric dimension of graph G which is the cardinality of minimal resolving set, then we have β(G) ≤ ψ(G) since every doubly resolving set is a resolving set, too. Borchert and Gosselin et al. solved the problem of finding metric dimension for Harary graph H4,n, n ≥ 8. In this paper, we find the minimal doubly resolving set, and hence the cardinality ψ(H4,n) for Harary graph H4,n, n ≥ 8.