On the strong edge metric dimension of graphs

Articles in Press

Document Type : Research Paper

Authors

1 Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, P. O. Box 1159-91775, Mashhad, Iran.

2 Department of Mathematics, University of Neyshabur, P.O.Box 91136-899, Neyshabur, Iran.

Abstract

A vertex $v$ in a connected graph $G$ strongly distinguishes two edges $e_1$ and $e_2$ if $\mathrm{d}(e_1,v)= \mathrm{d}(e_2,v)+\mathrm{d}(e_1,e_2)$ or $\mathrm{d}(e_2,v)= \mathrm{d}(e_1,v)+\mathrm{d}(e_1,e_2)$, where for an edge $e=xy$, $\mathrm{d}(e,v)=\mathrm{\min}\{\mathrm{d}(x,v),\mathrm{d}(y,v)\}$ and also the distance between two edges $e_1=xy$ and $e_2=uv$ is $\mathrm{d}(e_1,e_2)=\mathrm{\min}\{\mathrm{d}(e_1,u),\mathrm{d}(e_1,v)\}.$ A nonempty set $S \subseteq V(G)$ is a strong edge metric generator of a graph $G$ if for any two distinct edges $e_1,e_2 \in E(G)$, there exists a vertex $s \in S$ such that $s$ strongly distinguishes $e_1$ and $e_2$. A strong edge metric generating set with the smallest number of elements is called a strong edge metric basis of $G$ and the number of elements in a strong edge metric basis is called the strong edge metric dimension of $G$ and it is denoted by $\mathrm{sedim}(G)$. In this paper, we propose this concept as an extension of the strong metric dimension and we determine the strong edge metric dimension of several classes of graphs. Moreover, the $\mathrm{sedim}$ for the $G$-generalized join graph is investigated. Furthermore, we study the strong edge metric dimension of the comaximal graph of the ring of integers modulo $n$. Finally, we pose an integer linear programming model for finding the strong edge metric dimension of graphs.

Keywords

Main Subjects

References

[1] M. Afkhami, On the edge metric dimension and Wiener index of the blow up of graphs, NOTE MAT., 40 No. 2 (2021) 99-110.
[2] M. Afkhami, Z. Barati and K. Khashyarmanesh, On the signless Laplacian spectrum of the comaximal graphs, Asian-Eur. J. Math., 16 (2023) 2350055.
[3] A. Behtoei and Y. Golkhandy Pour, On two-dimensional Cayley graphs, Alg. Struc. Appl., 4 No. 1 (2017) 45-52.
[4] J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, Vol. 244, Springer, New York, 2008.
[5] J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara and D. R. Wood, On the metric dimension of cartesian products of graphs, SIAM J. Discrete Math., 21 No. 2 (2007) 423-441.
[6] K. Ch. Das and M. Tavakoli, Bounds for metric dimension and defensive k-alliance of graphs under deleted lexicographic product, Trans. Comb., 9 No. 1 (2020) 31-39.
[7] Leah L. Epstein, A. Levin and G. J. Woeginger, The (weighted) metric dimension of graphs: hard and easy cases, Algorithmica, 72 (2015) 1130-1171.
[8] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, New York, 1979.
[9] M. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat., 3 (1993) 203-236.
[10] A. Kelenc, N. Tratnik and I. G. Yero, Uniquely identifying the edges of a graph: The edge metric dimension, Discrete Appl. Math., 256 (2018) 204-220.
[11] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70 (1996) 217-229.
[12] J. Kratica, V. Kovačević-Vujčić, M. Čangalović and N. Mladenović, Strong metric dimension: a survey, Yugosl. J. Oper. Res., 24 No. 2 (2014) 187-198.
[13] D. Kuziak, I. G. Yero and J. A. Rodríguez-Velázquez, On the strong metric dimension of corona product graphs and join graphs, Discrete Appl. Math., 161 No. (7-8) (2013) 1022-1027.
[14] D. Kuziak, I. G. Yero and J. A. Rodríguez-Velázquez, On the strong metric dimension of the strong products of graphs, Open Math., 13 No. 1 (2015) 64-74.
[15] H. R. Maimani, M. Salimi, A. Sattari and S. Yassemi, Comaximal graph of commutative rings, J. Algebra, 319 (2008) 1801-1808.
[16] I. Peterin and I. G. Yero, Edge metric dimension of some graph operations, Bull. Malays. Math. Sci. Soc., 43 No. 3 (2020) 2465-2477.
[17] J. A. Rodríguez-Velázquez, I. G. Yero, D. Kuziak and O. R. Oellermann, On the strong metric dimension of Cartesian and direct products of graphs, Discrete Math., 335 (2014) 8-19.
[18] A. J. Schwenk, Computing the characteristic polynomial of a graph. In Graphs and Combinatorics: Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University June 18-22, 1973, pp. 153-172. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
[19] S. W. Saputro, R. Simanjuntak, S. Uttunggadewa, H. Assiyatun, E. T. Baskoro, A. N. M. Salman and M. Bača, The metric dimension of the lexicographic product of graphs, Discrete Math., 313 (2013) 1045-1051.
[20] P. K. Sharma and S. M. Bhatwadekar, A note on graphical representation of rings, J. Algebra, 176 (1995) 124-127.
[21] A. Sebo and E. M. Tannier, On metric generators of graphs, Math. Oper. Res., 29 No. 2 (2004) 383-393.
[22] P. J. Slater, Leaves of trees, Congr. Numer., 14 (1975) 549-559.
[23] M. M. Slavko and Z. Z. Petrovic, On the structure of comaximal graphs of commutative rings with identity, Bull. Aust. Math. Soc., 83 (2011) 11-21.
[24] M. Tavakoli, F. Rahbarnia and A. R. Ashrafi, Distribution of some graph invariants over hierarchical product of graphs, Appl. Math. Comput., 220 (2013) 405-413.
[25] H. J. Wang, Graphs associated to co-maximal ideals of commutative rings, J. Algebra, 320 (2008) 2917-2933.
[26] M. Young, Adjacency matrices of zero-divisor graphs of integers modulo n, Involve, 8 (2015) 753-761.
[27] N. Zubrilina, On the edge dimension of a graph, Discrete Math., 341 (2018) 2083-2088.
Algebraic Structures and Their Applications

Articles in Press, Corrected Proof
Available Online from 25 April 2026

Files

Share

How to cite

Statistics