×

Sharp bounds for partition dimension of generalized Möbius ladders. (English) Zbl 1407.05076

Summary: The concept of minimal resolving partition and resolving set plays a pivotal role in diverse areas such as robot navigation, networking, optimization, mastermind games and coin weighing. It is hard to compute exact values of partition dimension for a graphic metric space, \((G, d_{G})\) and networks. In this article, we give the sharp upper bounds and lower bounds for the partition dimension of generalized Möbius ladders, \(M_{m, n}\), for all \(n\geq 3\) and \(m\geq 2\).

MSC:

05C12 Distance in graphs
05C15 Coloring of graphs and hypergraphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Harary F., Melter R. A., On the metric dimension of a graph, Ars. Combinatoria, 1976, 2, 191-195.; Harary, F.; Melter, R. A., On the metric dimension of a graph, Ars. Combinatoria, 2, 191-195 (1976) · Zbl 0349.05118
[2] Sebo A., Tannier E., On metric generators of graphs, Math. Oper. Res., 2004, 29, 383-393.; Sebo, A.; Tannier, E., On metric generators of graphs, Math. Oper. Res., 29, 383-393 (2004) · Zbl 1082.05032
[3] Bogomonly A., and Greenwell D., Cut the knote: Invitition to Mastermind, 1999. .; Bogomonly, A.; Greenwell, D., Cut the knote: Invitition to Mastermind (1999)
[4] Chvatal V., Mastermind, Combinatorica, 1983, 3, 325-329.; Chvatal, V., Mastermind, Combinatorica, 3, 325-329 (1983) · Zbl 0717.05002
[5] Khuller S., Raghavachari B., Rosenfeld A., Landmarks in graphs, Disc. Appl. Math. 1996, 70, 217-229.; Khuller, S.; Raghavachari, B.; Rosenfeld, A., Landmarks in graphs, Disc. Appl. Math., 70, 217-229 (1996) · Zbl 0865.68090
[6] Frank P., Silverman R., Remarks on detection problems, Amer. Math. Monthly, 1967, 74, 171-173.; Frank, P.; Silverman, R., Remarks on detection problems, Amer. Math. Monthly, 74, 171-173 (1967) · Zbl 0157.49001
[7] Melter R.A., Tomescu I., Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing, 1984, 25, 113-121.; Melter, R. A.; Tomescu, I., Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing, 25, 113-121 (1984) · Zbl 0591.51023
[8] Chartrand G., Eroh L., Johnson M. A., Oellermann, O. R.,Resolvibility in graphs and the metric dimension of a grap, Disc. Appl. Math., 2000, 105, 99-133.; Chartrand, G.; Eroh, L.; Johnson, M. A.; Oellermann, O. R., Resolvibility in graphs and the metric dimension of a grap, Disc. Appl. Math., 105, 99-133 (2000) · Zbl 0958.05042
[9] Buczkowski P.S., Chartrand G., Poisson C., Zhang, P. On k-dimensional graphs and their bases, Pariodica Math. Hung, 2003, 46, 9-15.; Buczkowski, P. S.; Chartrand, G.; Poisson, C.; Zhang, P., On k-dimensional graphs and their bases, Pariodica Math. Hung, 46, 9-15 (2003) · Zbl 1026.05033
[10] 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., 2005, 22, 129-133.; 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., 22, 129-133 (2005) · Zbl 1182.05050
[11] Tomescu I., Javaid I., On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roumanie, 2007, 50, 371-376.; Tomescu, I.; Javaid, I., On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roumanie, 50, 371-376 (2007) · Zbl 1164.05019
[12] Javaid I., Rahim M.T., Ali K., Families of regular graphs with constant metric dimension, Utilitas Math., 2008, 75, 21-33.; 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] Shanmukha B., Sooryanarayana B., Harinath K. S., Metric dimension of wheels, Far East J. Appl. Math. 2002, 8, 217-229.; Shanmukha, B.; Sooryanarayana, B.; Harinath, K. S., Metric dimension of wheels, Far East J. Appl. Math., 8, 217-229 (2002) · Zbl 1032.05044
[14] Poisson C., Zhang P., The metric dimension of unicyclic graphs, J. Comb. Math Comb. Comput. 2002, 40, 17-32.; Poisson, C.; Zhang, P., The metric dimension of unicyclic graphs, J. Comb. Math Comb. Comput., 40, 17-32 (2002) · Zbl 0990.05040
[15] Hussain Z., Munir M., Chaudhary M., Kang S.M. Computing Metric Dimension and Metric Basis of 2D Lattice of Alpha-Boron Nanotubes, Symmetry 2018, 10, 300.; Hussain, Z.; Munir, M.; Chaudhary, M.; Kang, S. M., Computing Metric Dimension and Metric Basis of 2D Lattice of Alpha-Boron Nanotubes, Symmetry, 10, 300 (2018) · Zbl 1423.82050
[16] Murtaza A., Ali G., Imaran M., Baig A.Q., Kashif M., On the metric dimension of Möbius Ladder, ARS Combinatoria, 2012 105, 403-410.; Murtaza, A.; Ali, G.; Imaran, M.; Baig, A. Q.; Kashif, M., On the metric dimension of Möbius Ladder, ARS Combinatoria, 105, 403-410 (2012) · Zbl 1274.05119
[17] Munir M., Nizami A. R., Saeed H., Iqba Z., On the metric dimension of Möbius Ladder, ARS Combinatoria, 2017, 135, 239-245.; Munir, M.; Nizami, A. R.; Saeed, H.; Iqba, Z., On the metric dimension of Möbius Ladder, ARS Combinatoria, 135, 239-245 (2017) · Zbl 1463.05141
[18] Chartrand G., Poisson C., Zhang P., Resolvability and the upper dimension of graphs. Comput. Math. Appl., 2000, 39, 19-28.; Chartrand, G.; Poisson, C.; Zhang, P., Resolvability and the upper dimension of graphs, Comput. Math. Appl., 39, 19-28 (2000) · Zbl 0953.05021
[19] Slater P. J., Dominating and refrences sets in graphs, J. Math. Phys. sci., 1998, 22, 445-455.; Slater, P. J., Dominating and refrences sets in graphs, J. Math. Phys. sci., 22, 445-455 (1998) · Zbl 0656.05057
[20] Chartrand G., Salehi E., Zhang P., On the partition dimension of a graph, Congr. Numer., 1998, 131, 55-66.; Chartrand, G.; Salehi, E.; Zhang, P., On the partition dimension of a graph, Congr. Numer., 131, 55-66 (1998) · Zbl 0952.05021
[21] Chartrand G., Salehi E., Zhang P., The partition dimension of a graph, Aequationes Math, 2000, 59, 45-54.; Chartrand, G.; Salehi, E.; Zhang, P., The partition dimension of a graph, Aequationes Math, 59, 45-54 (2000) · Zbl 0939.05029
[22] Tomescu I., Imran M., On metric and partition dimensions of some infinite regular graphs, Bull. Math. Soc. Sci. Math. Roumanie 2009, 100, 461-472.; Tomescu, I.; Imran, M., On metric and partition dimensions of some infinite regular graphs, Bull. Math. Soc. Sci. Math. Roumanie, 100, 461-472 (2009) · Zbl 1199.05257
[23] Tomescu I., Imran M., Slamin M., On the partition dimension and connected partition dimension of wheels, Ars Combinatoria, 2007, 84, 311-317.; Tomescu, I.; Imran, M.; Slamin, M., On the partition dimension and connected partition dimension of wheels, Ars Combinatoria, 84, 311-317 (2007) · Zbl 1212.05258
[24] Chappell C., Glenn G., Gimbel J. Hartman C., Bounds on the metric and partition dimensions of a graph, Ars Combinatoria, 2008, 88, 349-366.; Chappell, C.; Glenn, G.; Gimbel, J.; Hartman, C., Bounds on the metric and partition dimensions of a graph, Ars Combinatoria, 88, 349-366 (2008) · Zbl 1224.05133
[25] Fernau H., Rodríguez-Velázquez J. A., Yero I. G., On the partition dimension of unicyclic graphs, Bull. Math. Soc. Sci. Math. Roumanie, Tome 2014, 57, 381-391.; Fernau, H.; Rodríguez-Velázquez, J. A.; Yero, I. G., On the partition dimension of unicyclic graphs, Bull. Math. Soc. Sci. Math. Roumanie, Tome, 57, 381-391 (2014) · Zbl 1389.05028
[26] Rojas A., Diaz K., Distance Labellings of Möbius Ladders, disertaion Worcester Polytechnic Institute 12-3-2013.; Rojas, A.; Diaz, K., Distance Labellings of Möbius Ladders, disertaion Worcester Polytechnic Institute
[27] Hongbin M., Idrees M., Nizami A.R., Munir M., Generalized Möbius Ladder and Its Metric Dimension, arXiv:1708.05199.; Hongbin, M.; Idrees, M.; Nizami, A. R.; Munir, M., Generalized Möbius Ladder and Its Metric Dimension
[28] Tang Z., Liang L., Gao W., Wiener polarity index of quasi-tree molecular structures, Open J. Math. Sci., 2018, 1, 73-83.; Tang, Z.; Liang, L.; Gao, W., Wiener polarity index of quasi-tree molecular structures, Open J. Math. Sci., 1, 73-83 (2018)
[29] Umar M.A., Javed M.A., Hussain M., Ali B.R., Super (a, d) - C 4 -antimagicness of book graphs Open J. Math. Sci., 2018, 2, 115-121.; Umar, M. A.; Javed, M. A.; Hussain, M.; Ali, B. R., Super (a, d) - C 4 -antimagicness of book graphs, Open J. Math. Sci., 2, 115-121 (2018)
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.