On metric dimension of \(P(n, 2)\odot K_1\) graph. (English) Zbl 1483.05051
Summary: For a connected graph \(G\), a subset \(W = \{w_1, w_2, w_3, \dots, w_\xi \}\) of the vertices of \(G\) is the resolving set for \(G\) if for \(a, b \in V(G)\), we have \(d(a, (w_\xi) \neq d(b, w_\xi)\) for all \(w_\xi \in W\). Metric basis for \(G\) is the minimum number of vertices in \(W\) and metric dimension is the cardinality of such a set denoted by \(\beta (G)\). In this paper we compute the metric dimension of \(P(n, 2)\odot K_1\).
MSC:
| 05C12 | Distance in graphs |
| 05C40 | Connectivity |
| 05C90 | Applications of graph theory |
| 05C76 | Graph operations (line graphs, products, etc.) |
References:
| [1] | Bača, M., Labellings of two classes of convex polytopes, Utilitas Math, 34, 24-31 (1988) · Zbl 0662.05025 |
| [2] | Bača, M., On magic labellings of convex polytopes, Annals Disc. Math, 51, 13-16 (1992) · Zbl 0763.05089 · doi:10.1016/S0167-5060(08)70599-5 |
| [3] | Buczkowski, P. S.; Chartrand, G.; Poisson, C.; Zhang, P., On k-dimensional graphs and their bases, Periodica Math. Hung, 46, 1, 9-15 (2003) · Zbl 1026.05033 · doi:10.1023/A:1025745406160 |
| [4] | Caceres, J.; Hernando, C.; Mora, M.; Pelayo, I. M.; Puertas, M. L.; Seara, C.; Wood, D. R., On the metric dimension of some families of graphs, Electronic Notes in Disc. Math, 129-133 (2005) · Zbl 1182.05050 · doi:10.1016/j.endm.2005.06.023 |
| [5] | Caceres, J.; Hernando, C.; Mora, M.; Pelayo, I. M.; Puertas, M. L.; Seara, C.; Wood, D. R., On the metric dimension of Cartesian product of graphs, SIAM J. Disc. Math, 2, 21, 423-441 (2007) · Zbl 1139.05314 · doi:10.1137/050641867 |
| [6] | Chartrand, G.; Zhang, P., The theory and applications of resolvability in graphs, Congress. Numer, 160, 47-68 (2003) · Zbl 1039.05029 |
| [7] | Chartrand, G.; Eroh, L.; Johnson, M. A.; Oellermann, O. R., Resolvability in graphs and metric dimension of a graph, Disc. Appl. Math, 105, 99-113 (2000) · Zbl 0958.05042 · doi:10.1016/S0166-218X(00)00198-0 |
| [8] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman, New York · Zbl 0411.68039 |
| [9] | Harary, F.; Melter, R. A., On the metric dimension of a graph, Ars Combin, 2, 191-195 (1976) · Zbl 0349.05118 |
| [10] | Imran, M.; Baig, A. Q.; Ahmad, A., Families of plane graphs with constant metric dimension, Utilitas Math, 88, 43-57 (2012) · Zbl 1255.05056 |
| [11] | Imran, M., Baig, A. Q., Shafiq, M. K., Tomescu, I., On metric dimension of generalized Petersen graphs P(n; 3), to appear in Ars Combin. · Zbl 1349.05090 |
| [12] | Javaid, I.; Rahim, M. T.; Ali, K., Families of regular graphs with constant metric dimension, Utilitas Math, 75, 21-33 (2008) · Zbl 1178.05037 |
| [13] | Johnson, M. A., Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Statist, 3, 203-236 (1993) · Zbl 0800.92106 · doi:10.1080/10543409308835060 |
| [14] | Jucovič, E., Convex polyhedra, Veda, Bratislava, 1981 (in Slovak). · Zbl 0468.52007 |
| [15] | Khuller, S., Raghavachari, B., Rosenfeld, A., Localization in graphs, Technical Report CS-TR-3326, University of Maryland at College Park, 1994. · Zbl 0865.68090 |
| [16] | Khuller, S.; Raghavachari, B.; Rosenfeld, A., Landmarks in graphs, Disc. Appl. Math, 70, ); 217-229 (1996) · Zbl 0865.68090 · doi:10.1016/0166-218X(95)00106-2 |
| [17] | Melter, R. A.; Tomescu, I., Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing, 25, 113-121 (1984) · Zbl 0591.51023 · doi:10.1016/0734-189X(84)90051-3 |
| [18] | Mphako-Banda, E., Some polynomials of flower graphs, International Math. Forum, 2, 51, 2511-2518 (2007) · Zbl 1140.05330 · doi:10.12988/imf.2007.07221 |
| [19] | Oellermann, O. R.; Peters-Fransen, J., Metric dimension of Cartesian products of graphs, Utilitas Math, 69, 33-41 (2006) · Zbl 1109.05041 |
| [20] | Slater, P. J., Leaves of trees, Congress, Numer, 14, 549-559 (1975) · Zbl 0316.05102 |
| [21] | Slater, P. J., Dominating and reference sets in graphs, J. Math. Phys. Sci, 22, 445-455 (1998) · Zbl 0656.05057 |
| [22] | Tomescu, I.; Javaid, I., On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roum, 4, 98, 371-376 (2007) · Zbl 1164.05019 |
| [23] | Tomescu, I.; Imran, M., On metric and partition dimensions of some infinite regular graphs, Bull. Math. Soc. Sci. Math. Roum, 52, 100, 461-472 (2009) · Zbl 1199.05257 |
| [24] | Yan, L.; Li, Y.; Zhang, X.; Saqlain, M.; Zafar, S.; Farahani, M. R., 3-total edge product cordial labeling of some new classes of graphs, Journal of Information & Optimization Sciences, 39, 3, 705-724 (2018) · doi:10.1080/02522667.2017.1417727 |
| [25] | Rosyida, I.; Ningrum, E.; Mulyono, D. Indriati., On Total Vertex and Edge Irregularity Strengths, Journal of Discrete Mathematical Sciences and Cryptography, 23, 6, 1335-1358 (2020) · Zbl 1482.05302 · doi:10.1080/09720529.2020.1820704 |
| [26] | Rosyida, I.; Mulyono, D. Indriati., On Total Vertex Irregularity Strengths of Uniform Cactus Chains, Journal of Discrete Mathematical Sciences and Cryptography, 23, 6, 1369-1380 (2020) · Zbl 1482.05301 · doi:10.1080/09720529.2020.1830562 |
| [27] | Mohammed, M. A.; Munshid, A. J.; Siddiqui, H. M.A.; Farahani, M. R., Computing the metric and partition dimension of tessellation of plane by boron nanosheets, Eurasian Chem. Commun, 2, 1064-1071 (2020) · doi:10.22034/ECC.2020.251927.1083 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
