Research article

On the edge metric dimension of graphs

  • Received: 17 March 2020 Accepted: 10 May 2020 Published: 18 May 2020
  • MSC : 05C40

  • 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.

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

    Related Papers:

  • 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.


    加载中


    [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. doi: 10.1007/s00025-018-0927-1
    [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. doi: 10.1016/j.dam.2018.05.052
    [5] I. Peterin, I. G. Yero, Edge metric dimension of some graph operations, B. Malays. Math. Sci. So., 43 (2020), 2465-2477. doi: 10.1007/s40840-019-00816-7
    [6] N. Zubrilina, On the edge dimension of a graph, Discrete Math., 341 (2018), 2083-2088. doi: 10.1016/j.disc.2018.04.010
    [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. doi: 10.1016/j.dam.2018.08.031
  • Reader Comments
  • © 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(319) PDF downloads(278) Cited by(1)

Article outline

Figures and Tables

Figures(2)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog