Abstract
The metric dimension is a fundamental concept in graph theory that utilizes the vector representation of distances between vertices and a subset of vertices in a graph. This concept has broad applications in various fields, such as navigation, network localization, and network design. Let G(V,E) be a connected graph with order n . A subset L={v1,v2,v3} subset of V(G) is called a resolving set, and the representation of a vertex v with respect to L is a vector (d(v,v1), d(v,v2)..d(v,vk)) , where d(v,vi) is the distance between v and vi . The metric dimension of G, denoted as dim(G), is the smallest cardinality of L such that every vertex in G has a unique representation. The windmill graph K1+nK3 is a graph obtained by connecting a vertex x in the complete graph K1 to every vertex in n copies of the complete graph K3. This paper employs a structural analysis method focused on the single vertex in K1 and determines the vector representations of all vertices in the windmill graph by analyzing inter-vertex distances. The final result shows that the metric dimension, dim (K1+nK3)= 2n, where n is an integer grether than 2 .
Keywords:
Wildmill graph metrik dimension vertex representation complete graphReferences
Ali, G., Laila, R., & Ali, M. (2016). Metric dimension of some families of graph. Math. Sci. Lett., 5(1), 99–102.
Bailey, R. F., & Cameron, P. J. (2011). Base size, metric dimension and other invariants of groups and graphs. Bulletin of the London Mathematical Society, 43, 209–242.
Beardon, A. F., & Rodríguez-Velázquez, J. A. (2019). On the k-metric dimension of metric spaces. Ars Mathematica Contemporanea, 16, 25–38.
Blumenthal, L. M. (1953). Theory and Applications of Distance Geometry. Clarendon Press.
Cáceres, J., Hernando, C., Mora, M., Pelayo, I. M., Puertas, M. L., Seara, C., & Wood, D. R. (2007). On the metric dimension of Cartesian products of graphs. SIAM Journal on Discrete Mathematics, 21, 423–441.
Chappell, G. G., Gimbel, J., & Hartman, C. (2008). Bounds on the metric and partition dimensions of a graph. Ars Combinatoria, 88, 349–366.
Chartrand, G., Eroh, L., Johnson, M. A., & Oellermann, O. R. (2000). Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics, 105, 99–113.
Chartrand, G., Salehi, E., & Zhang, P. (2000). The partition dimension of a graph. Aequationes Mathematicae, 59, 45–54.
Estrada-Moreno, A., Rodríguez-Velázquez, J. A., & Yero, I. G. (2015). The k-metric dimension of a graph. Applied Mathematics & Information Sciences, 9(6), 2829–2840.
Estrada-Moreno, A., Rodríguez-Velázquez, J. A., & Yero, I. G. (2016). The k-metric dimension of corona product graphs. Bulletin of the Malaysian Mathematical Sciences Society, 39, 135–156.
Estrada-Moreno, A., Rodríguez-Velázquez, J. A., & Yero, I. G. (2016). The k-metric dimension of the lexicographic product of graphs. Discrete Mathematics, 339(7), 1924–1934.
Estrada-Moreno, A., Rodríguez-Velázquez, J. A., & Yero, I. G. (2020). On the (k, t)-metric dimension of graphs. The Computer Journal. https://doi.org/10.1093/comjnl/bxaa009
Fehr, M., Gosselin, S., & Oellermann, O. R. (2006). The partition dimension of Cayley digraphs. Aequationes Mathematicae, 71(1–2), 1–18.
Harary, F., & Melter, R. A. (1976). On the metric dimension of a graph. Ars Combinatoria, 2, 191–195.
Haynes, T. W., Henning, M. A., & Howard, J. (2006). Locating and total dominating sets in trees. Discrete Applied Mathematics, 154, 1293–1300.
Johnson, M. (1993). Structure–activity maps for visualizing the graph variable arising in drug design. Journal of Biopharmaceutical Statistics, 3(2), 203–236.
Johnson, M. (1998). Browsable structure–activity datasets. In R. Carbó-Dorca & P. Mezey (Eds.), Advances in Molecular Similarity (Chap. 8). JAI Press Inc.
Karpovsky, M. G., Chakrabarty, K., & Levitin, L. B. (1998). On a new class of codes for identifying vertices in graphs. IEEE Transactions on Information Theory, 44, 599–611.
Khuller, S., Raghavachari, B., & Rosenfeld, A. (1996). Landmarks in graphs. Discrete Applied Mathematics, 70(3), 217–229.
Melter, R. A., & Tomescu, I. (1984). Metric bases in digital geometry. Computer Vision, Graphics, and Image Processing, 25(1), 113–121.
Okamoto, F., Phinezy, B., & Zhang, P. (2010). The local metric dimension of a graph. Mathematica Bohemica, 135, 239–255.
Saenpholphat, V., & Zhang, P. (2004). Conditional resolvability in graphs: A survey. International Journal of Mathematics and Mathematical Sciences, 38, 1997–2017.
Slater, P. J. (1975). Leaves of trees. Congressus Numerantium, 14, 549–559.
Slater, P. J. (1988). Dominating and reference sets in a graph. Journal of Mathematical and Physical Sciences, 22(4), 445–455.
Tomescu, I. (2008). Discrepancies between metric dimension and partition dimension of a connected graph. Discrete Applied Mathematics, 308(22), 5026–5031.
Ungrangsi, R., Trachtenberg, A., & Starobinski, D. (2004). An implementation of indoor location detection systems based on identifying codes. In Proceedings of Intelligence in Communication Systems, INTELLCOMM 2004 (Vol. 3283, pp. 175–189).
Yero, I. G., Estrada-Moreno, A., & Rodríguez-Velázquez, J. A. (2017). Computing the k-metric dimension of graphs. Applied Mathematics and Computation, 300, 60–69. https://doi.org/10.1016/j.amc.2016.12.005
Yero, I. G., Kuziak, D., & Rodríguez-Velázquez, J. A. (2011). On the metric dimension of corona product graphs. Computers & Mathematics with Applications, 61, 2793–2798.
Yero, I. G., & Rodríguez-Velázquez, J. A. (2010). A note on the partition dimension of Cartesian product graphs. Applied Mathematics and Computation, 217(7), 3571–3574.
License
Copyright (c) 2024 Amrullah Amrullah, Harry Soeprianto, Ketut Sarjana, Laila Hayati
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
