Name
Abstract | ||
|---|---|---|
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 dime(G). It follows that 1≤dime(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(n3) 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.dam.2018.08.031 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Edge metric generator,Edge metric dimension,Upper bound,Algorithm | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Upper and lower bounds,Vertex (graph theory),Cardinality,Connectivity,Metric dimension,Mathematics | Journal |
Volume | ISSN | Citations |
257 | 0166-218X | 1 |
PageRank | References | Authors |
0.40 | 4 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Enqiang Zhu | 1 | 25 | 11.99 |
| Enqiang Zhu | 2 | 25 | 11.99 |
| Andrej Taranenko | 3 | 43 | 4.90 |
| Zehui Shao | 4 | 119 | 30.98 |
| Jin Xu | 5 | 230 | 45.13 |