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

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

Abstract
Full Text(HTML)

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.
- edge metric dimension,
- clique number,
- bipartite graphs
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:

Abstract

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.

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

your name:*

Email:*
© 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)