On metric dimension of edge comb product of vertex-transitive graphs

Document Type : Research Paper

Authors

1 Department of Mathematics Education, Syarif Hidayatullah State Islamic University Jakarta, Indonesia

2 Department of Mathematics, Faculty of Mathematics and Natural Sciences, Bandung Institute of Technology, Indonesia

10.22108/toc.2024.133850.1991

Abstract

Suppose finite graph $G$ is simple, undirected and connected. If $W$ is an ordered set of the vertices such that $|W| = k$, the representation of a vertex $v$ is an ordered $k$-tuple consisting distances of vertex $v$ with every vertices in $W$. The set $W$ is defined as resolving vertex of $G$ if the $k$-tuples of every two vertices are distinct. Metric dimension of $G$, which is denoted by $dim(G)$, is the lowest size of $W$. In this paper, we provide a sharp lower bound of metric dimension for edge comb product graphs $G \cong T$ ▷e $H$ where $T$ is a tree graph and $H$ is a vertex-transitive graph. Moreover, we determine the exact value of metric dimension for edge comb product graphs $G \cong T$ ▷e $Ci_n(1,2)$ where $Ci_n(1,2)$ is a circulant graph.

Keywords

Main Subjects

References

[1] Z. Y. Awanis, A. N. M. Salman and S. W. Saputro, The strong 3-rainbow index of edge-comb product of a path and a connected graph, Electron. J. Graph Theory Appl. (EJGTA), 10 no. 1 (2022) 33–50.
[2] A. Borchert and S. Gosselin, The metric dimension of circulant graphs and Cayley hypergraphs, Util. Math., 106 (2018) 125–147. (2014).
[3] J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara and D. R. Wood, On the metric dimension of some families of graphs, Electron. Notes Discrete Math., 22 (2005) 129–133.
[4] G. Chartrand, L. Eroh, M. A. Johnson and O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105 no. 1-3 (2000) 99–113.
[5] H. Fernau, P. Heggernes, P. van’t Hof, D. Meister and R. Saei, Computing the metric dimension for chain graphs, Inform. Process. Lett., 115 (2015) 671–676.
[6] W. Goddard, Static mastermind, J. Combin. Math. Combin. Comput., 47 (2003) 225–236.
[7] F. Harary and R. A. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976) 191–195.
[8] M. Imran, A. Q. Baig, S. A. U. H. Bokhary and I. Javaid, On the metric dimension of circulant graphs, Appl. Math. Lett., 25 no. 3 (2012) 320–325.
[9] H. Iswadi, E. T. Baskoro, A. N. M. Salman and R. Simanjuntak, The metric dimension of amalgamation of cycles, Far East J. Math. Sci. (FJMS), 41 no. 1 (2010) 19–31.
[10] H. Iswadi, H. Assiyatun, A. N. M. Salman and E. T. Baskoro, Metric dimension of antipodal and pendant-free block-cactus graphs, (2009). http://www.jaist.ac.jp/$\sim$uehara/JCCGG09/short/paper_31.pdf.
[11] M. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat., 3 no. 2 (1993) 203–236.
[12] M. Johnson, Browsable structure-activity datasets, Adv. in Mol. Similarity, 2 (1998) 153–170.
[13] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70 no. 3 (1996) 217–229.
[14] S. W. Saputro, N. Mardiana and I. Purwasih, The metric dimension of comb product graph, Mat. Vesnik, 69 no. 4 (2017) 248–258.
[15] Slamin, Dafik and A. G. Waspodo, Distance domination number of graphs resulting from edge comb product, J. Phys.: Conf. Ser., 1022 (2018) 012008.
[16] P. J. Slater, Leaves of trees, Proc. 6th Southeastern Conf. on Comb. Graph Theory Comput., 14 (1975) 549–559.
[17] T. Vetrı́k, On the metric dimension of directed and undirected circulant graphs, Discuss. Math. Graph Theory, 40 no. 1 (2020) 67–76.
[18] I. G. Yero, D. Kuziak and J. A. Rodrı́guez-Velázquez, On the metric dimension of corona product graphs, Comput. Math. Appl., 61 (2011) 2793–2798.
Transactions on Combinatorics

Articles in Press, Corrected Proof
Available Online from 27 April 2024

Files

History

  • Receive Date: 27 May 2022
  • Revise Date: 18 September 2023
  • Accept Date: 02 March 2024
  • Published Online: 27 April 2024

Share

How to cite

Statistics