AIMS Mathematics, 2020, 5(5): 4459-4465. doi: 10.3934/math.2020286.

Research article

Export file:

Format

  • RIS(for EndNote,Reference Manager,ProCite)
  • BibTex
  • Text

Content

  • Citation Only
  • Citation and Abstract

On the edge metric dimension of graphs

1 College of Arts and Sciences, Shanghai Maritime University, Shanghai 201306, China
2 School of Mathematics and Statistics, Shandong Normal University, Jinan 250358, Shandong, China
3 School of Mathematics and Statistics, Ningbo University, Ningbo 315211, Zhejiang, China

Let $G=(V,E)$ be a connected graph of order $n$. $S \subseteq V$ is an edge metric generator of $G$ if any pair of edges in $E$ can be distinguished by some element of $S$. The edge metric dimension $edim(G)$ of a graph $G$ is the least size of an edge metric generator of $G$. In this paper, we give the characterization of all connected bipartite graphs with $edim=n-2$, which partially answers an open problem of Zubrilina (2018). Furthermore, we also give a sufficient and necessary condition for $edim(G)=n-2$, where $G$ is a graph with maximum degree $n-1$. In addition, the relationship between the edge metric dimension and the clique number of a graph $G$ is investigated by construction.
  Figure/Table
  Supplementary
  Article Metrics

Keywords edge metric dimension; clique number; bipartite graphs

Citation: Meiqin Wei, Jun Yue, Xiaoyu zhu. On the edge metric dimension of graphs. AIMS Mathematics, 2020, 5(5): 4459-4465. doi: 10.3934/math.2020286

References

  • 1. J. A. Bondy, U. S. R Murty, Graph Theory, GTM 244, Springer-Verlag, New York, 2008.
  • 2. R. Diestel, Graph Theory, GTM 173, Springer-Verlag, Heidelberg, 2005.
  • 3. V. Filipovíc, A. Kartelj, J. Kratica, Edge metric dimension of some generalized Petersen graphs, Results Math., 74 (2019), 1-15.    
  • 4. A. Kelenc, N. Tratnik, I. G. Yero, Uniquely identifying the edges of a graph: The edge metric dimension, Discrete Appl. Math., 251 (2018), 204-220.    
  • 5. I. Peterin, I. G. Yero, Edge metric dimension of some graph operations, B. Malays. Math. Sci. So., 43 (2020), 2465-2477.    
  • 6. N. Zubrilina, On the edge dimension of a graph, Discrete Math., 341 (2018), 2083-2088.    
  • 7. N. Zubrilina, On the edge metric dimension for the random graph, arXiv:1612.06936.
  • 8. E. Zhu, A. Taranenko, Z. Shao, et al. On graphs with the maximum edge metric dimension, Discrete Appl. Math., 257 (2019), 317-324.    

 

Reader Comments

your name: *   your email: *  

© 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution Licese (http://creativecommons.org/licenses/by/4.0)

Download full text in PDF

Export Citation

Copyright © AIMS Press All Rights Reserved