Metric dimension of lexicographic product of some known‎ ‎graphs

Document Type : Research Paper

Author

Department of Science, Shahreza Campus, University of Isfahan, Iran

Abstract

‎For an ordered set $W=\{w_1,w_2,\ldots,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the ordered $k$-vector $r(v|W):=(d(v,w_1),d(v,w_2),\ldots,d(v,w_k))$ is  called  the (metric) representation of $v$ with respect to $W$, where $d(x,y)$ is the distance between the vertices $x$ and $y$. The set $W$ is called  a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. The minimum cardinality of a resolving set for $G$ is its metric dimension. In this paper, we investigate the metric dimension of the lexicographic product  of graphs $G$ and $H$, $G[H]$, for some known graphs.

Keywords

Main Subjects

References

[1] Bailey, RF., & Cameron, PJ. (2011). Base size, metric dimension and other invariants of groups and graphs, Bull. London Math. Soc. 43 (2011) 209-242. https://doi.org/10.1112/blms/bdq096
[2] Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Ho mann, M., Mihalak, M., & Ram, LS. (2006). Network dicovery and veri cation, IEEE Journal On Selected Areas in Communications 24(12) 2168-2181. https://doi.org/10.1109/JSAC.2006.884015
[3] Behtoei, A. & Anbarloei, M. (2014) The locating chromatic number of the join of graphs, Bull. Iranian Math. Soc. 40(6) 1491-1504.
[4] Buczkowski, PS., Chartrand, G., Poisson,C., & Zhang, P.(2003) On k-dimensional graphs and their bases, Periodica Mathematica Hungarica 46(1) 9-15. DOI:10.1023/A:1025745406160
[5] Caceres, J., Hernando, C., Mora, M., Pelayo, IM., Puertas, ML., Seara, C., & Wood, D.R. (2007) On the metric dimension of cartesian products of graphs, SIAM Journal Discrete Mathematics 21(2) 423-441. DOI:10.1137/050641867
[6] Chartrand, G., Eroh, L., Johnson, MA., & Ollermann OR. 2000) Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics 105 ( 99-113). https://doi.org/10.1016/S0166-218X(00)00198-0
[7] Harary, F., & Melter, RA. (1976) On the metric dimension of a graph, Ars Combinatoria 2 191-195.
[8] Hernando, C., Mora, M., Pelayo, IM., Seara, C., & Wood, DR. (2010) Extremal Graph Theory for Metric Dimension and Diameter, The Electronic Journal of Combinatorics 17 #R30. DOI:10.37236/302
[9] Jannesari, M., & Omoomi, M. (2012) The metric dimension of the lexicographic product of graphs, Discrete  Mathematics. 312(22) (2012) 3349-3356. https://doi.org/10.1016/j.disc.2012.07.025
[10] Khuller, S., Raghavachari, B., & Rosenfeld, A. (1996) Landmarks in graphs, Discrete Applied Mathematics 70(3) 217-229. https://doi.org/10.1016/0166-218X(95)00106-2
[11] Melter, RA. & Tomescu, I. (1984) Metric bases in digital geometry, Computer Vision Graphics and Image Processing 25 113-121. https://doi.org/10.1016/0734-189X(84)90051-3
[12] Sebo, A., & Tannier, E. (2004) On metric generators of graphs, Mathematics of Operations Research 29(2) 383-393. https://doi.org/10.1287/moor.1030.0070
[13] Slater, P.J. (1975) Leaves of trees, Congressus Numerantium 14 549-559.
Journal of Mahani Mathematical Research
Volume 13, Issue 1 - Serial Number 26
November 2023
Pages 269-277

Files

History

  • Receive Date: 03 January 2023
  • Revise Date: 24 April 2023
  • Accept Date: 24 June 2023

Share

How to cite

Statistics