On graphs with the maximum edge metric dimension

An edge metric generator of a connected graph G is a vertex subset S for which every two distinct edges of G have distinct distance to some vertex of S, where the distance between a vertex v and an edge e is defined as the minimum of distances between v and the two endpoints of e in G. The smallest cardinality of an edge metric generator of G is the edge metric dimension, denoted by dim(e)(G). It follows that 1 <= dim(e)(G) <= n-1 for any n-vertex graph G. A graph whose edge metric dimension achieves the upper bound is topful. In this paper, the structure of topful graphs is characterized, and many necessary and sufficient conditions for a graph to be topful are obtained. Using these results we design an O(n(3) ) time algorithm which determines whether a graph of order n is topful or not. Moreover, we describe and address an interesting class of topful graphs whose super graphs obtained by adding one edge are not topful. (C) 2018 Elsevier B.V. All rights reserved.