The dominant edge metric dimension of graphs

Mostafa Tavakoli, Meysam Korivand, Ahmad Erfanian, Gholamreza Abrishami, Edy Tri Baskoro


For an ordered subset S = {v1, …, vk} of vertices in a connected graph G and an edge e′ of G, the edge metric S-representation of e′=ab is the vector rGe(e′|S)=(dG(e′,v1),…,dG(e′,vk)) , where dG(e′,vi)=min{dG(a, vi),dG(b, vi)}. A dominant edge metric generator for G is a vertex cover S of G such that the edges of G have pairwise different edge metric S-representations. A dominant edge metric generator of smallest size of G is called a dominant edge metric basis for G. The size of a dominant edge metric basis of G is denoted by Ddime(G) and is called the dominant edge metric dimension. In this paper, the concept of dominant edge metric dimension (DEMD for short) is introduced and its basic properties are studied. Moreover, NP-hardness of computing DEMD of connected graphs is proved. Furthermore, this invariant is investigated under some graph operations at the end of the paper.


dominant edge metric generator, edge metric dimension, vertex cover

Full Text:




S. El-Basil, Caterpillar(Gutman) trees in chemical graph theory, Topics in Current Chemistry 153 (1990) 273–289.

G. Chartrand, L. Eroh, Mark A. Johnson, Ortrud R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99-113.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, McGraw-Hill book company, The MIT Press, second edition, 2003.

M. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat. 3 (1993) 203–236 .

Y. Hou, W-C. Shiu, The spectrum of the edge corona of two graphs, Electron. J. Lin. Alg. 20 (2010) 586–594.

Richard M. Karp, Reducibility among combinatorial problems. Complexity of computer computations. Springer, Boston, MA, (1972). 85–103.

A. Kelenc, N. Tratnik, I. G. Yero, Uniquely identifying the edges of a graph: The edge metric dimension, Discrete Appl. Math. 256 (2018) 204–220.

S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217–229 .

F. Okamoto , L. Crosse , B. Phinezy , P. Zhang , The local metric dimension of a graph, Math. Bohem. 135 (2010) 239–255 .

P. J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.

Liliek Susilowati, Imroatus Sa’adah, Ratna Zaidatul Fauziyyah, Ahmad Erfanian, Slamin, The dominant metric dimension of graphs, Heliyon 6 (2020) e03633

M. Tavakoli, S. Klavžar, Distribution of global defensive k-alliances over some graph products, Cent. Eur. J. Oper. Res. 27 (2019) 615–623.

M. Tavakoli, F. Rahbarnia, A. R. Ashrafi, Studying the Corona Product of Graphs under some Graph Invariants, Trans. Comb. (2014) 43–49.

E. Zhu, A. Taranenko, Z. Shao, and J. Xu, ‘‘On graphs with the maximum edge metric dimension,’’Discrete Appl. Math. 257, (2019) 317–324.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats