On bounded partition dimension of different families of convex polytopes with pendant edges

Adnan Khali; Sh. K Said Husain; Muhammad Faisal Nadeem; Adnan Khali; Sh. K Said Husain; Muhammad Faisal Nadeem

doi:10.3934/math.2022245

AIMS Mathematics

2022, Volume 7, Issue 3: 4405-4415. doi: 10.3934/math.2022245

Previous Article Next Article

Research article Special Issues

On bounded partition dimension of different families of convex polytopes with pendant edges

1.
Department of Mathematics and Statistics, Faculty of Science, Universiti Putra Malaysia, 43400 Serdang, Selangor, Malaysia
2.
Laboratory of Cryptography, Analysis and Structure, Institute for Mathematical Research (INSPEM), Universiti Putra Malaysia, 43400 Serdang, Selangor, Malaysia
3.
Department of Mathematics, COMSATS University Islamabad, Lahore Campus, Lahore 54000 Pakistan

Received: 18 April 2021 Revised: 04 June 2021 Accepted: 23 September 2021 Published: 21 December 2021
MSC : 05C12, 05C76

Let $ \psi = (V, E) $ be a simple connected graph. The distance between $ \rho_1, \rho_2\in V(\psi) $ is the length of a shortest path between $ \rho_1 $ and $ \rho_2. $ Let $ \Gamma = \{\Gamma_1, \Gamma_2, \dots, \Gamma_j\} $ be an ordered partition of the vertices of $ \psi $. Let $ \rho_1\in V(\psi) $, and $ r(\rho_1|\Gamma) = \{d(\rho_1, \Gamma_1), d(\rho_1, \Gamma_2), \dots, d(\rho_1, \Gamma_j)\} $ be a $ j $-tuple. If the representation $ r(\rho_1|\Gamma) $ of every $ \rho_1\in V(\psi) $ w.r.t. $ \Gamma $ is unique then $ \Gamma $ is the resolving partition set of vertices of $ \psi $. The minimum value of $ j $ in the resolving partition set is known as partition dimension and written as $ pd(\psi). $ The problem of computing exact and constant values of partition dimension is hard so one can compute bound for the partition dimension of a general family of graph. In this paper, we studied partition dimension of the some families of convex polytopes with pendant edge such as $ R_n^P $, $ D_n^p $ and $ Q_n^p $ and proved that these graphs have bounded partition dimension.
- resolving partition set,
- bounded partition dimension,
- convex polytopes
Citation: Adnan Khali, Sh. K Said Husain, Muhammad Faisal Nadeem. On bounded partition dimension of different families of convex polytopes with pendant edges[J]. AIMS Mathematics, 2022, 7(3): 4405-4415. doi: 10.3934/math.2022245

Related Papers:

Abstract

Let $ \psi = (V, E) $ be a simple connected graph. The distance between $ \rho_1, \rho_2\in V(\psi) $ is the length of a shortest path between $ \rho_1 $ and $ \rho_2. $ Let $ \Gamma = \{\Gamma_1, \Gamma_2, \dots, \Gamma_j\} $ be an ordered partition of the vertices of $ \psi $. Let $ \rho_1\in V(\psi) $, and $ r(\rho_1|\Gamma) = \{d(\rho_1, \Gamma_1), d(\rho_1, \Gamma_2), \dots, d(\rho_1, \Gamma_j)\} $ be a $ j $-tuple. If the representation $ r(\rho_1|\Gamma) $ of every $ \rho_1\in V(\psi) $ w.r.t. $ \Gamma $ is unique then $ \Gamma $ is the resolving partition set of vertices of $ \psi $. The minimum value of $ j $ in the resolving partition set is known as partition dimension and written as $ pd(\psi). $ The problem of computing exact and constant values of partition dimension is hard so one can compute bound for the partition dimension of a general family of graph. In this paper, we studied partition dimension of the some families of convex polytopes with pendant edge such as $ R_n^P $, $ D_n^p $ and $ Q_n^p $ and proved that these graphs have bounded partition dimension.

References

[1]	Amrullah, S. Azmi, H. Soeprianto, M. Turmuzi, Y. S. Anwar, The partition dimension of subdivision graph on the star, J. Phys. Conf. Ser., 1280 (2019), 022037. http://dx.doi.org/10.1088/1742-6596/1280/2/022037 doi: 10.1088/1742-6596/1280/2/022037
[2]	M. Bača, Labellings of two classes of convex polytopes, Utilitas Math., 34 (1988), 24–31.
[3]	M. Bača, On magic labellings of convex polytopes, Ann. Discrete Math., 51 (1992), 13–16. https://doi.org/10.1016/S0167-5060(08)70599-5 doi: 10.1016/S0167-5060(08)70599-5
[4]	P. S. Buczkowski, G. Chartrand, C. Poisson, P. Zhang, On k-dimensional graphs and their bases, Period. Math. Hung., 46 (2003), 9–15. https://doi.org/10.1023/A:1025745406160 doi: 10.1023/A:1025745406160
[5]	Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihalak, et al. Network discovery and verification, IEEE J. Sel. Area. Comm., 24 (2006), 2168–2181. https://doi.org/10.1109/JSAC.2006.884015 doi: 10.1109/JSAC.2006.884015
[6]	G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105 (2000), 99–113. https://doi.org/10.1016/S0166-218X(00)00198-0 doi: 10.1016/S0166-218X(00)00198-0
[7]	G. Chartrand, E. Salehi, P. Zhang, The partition dimension of graph, Aequationes Math., 59 (2000), 45–54. https://doi.org/10.1007/PL00000127 doi: 10.1007/PL00000127
[8]	G. Chartrand, P. Zhang, The theory and applications of resolvability in graphs, Congr. Numer., 160 (2003), 47–68.
[9]	J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, et al. On the metric dimension of Cartesian product of graphs, SIAM J. Discrete Math., 21 (2007), 423–441. https://doi.org/10.1137/050641867 doi: 10.1137/050641867
[10]	V. Chvatal, Mastermind, Combinatorica, 3 (1983), 325–329. https://doi.org/10.1007/BF02579188
[11]	F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combinatoria, 1976 (1976), 191–195.
[12]	M. Imran, S. A. Bokhary, A. Q. Baig, On families of convex polytopes with constant metric dimension, Comput. Math. Appl., 60 (2010), 2629–2638. https://doi.org/10.1016/j.camwa.2010.08.090 doi: 10.1016/j.camwa.2010.08.090
[13]	M. Imran, A. Q. Baig, A. Ahmad, Families of plane graphs with constant metric dimension, Utilitas Math., 88 (2012), 43–57.
[14]	M. Imran, S. A. U. H. Bokhary, A. Q. Baig, I. Tomescu, On metric dimension of convex polytopes with pendant edges, Ars Combinatoria, 125 (2016), 433–447.
[15]	I. Javaid, M. T. Rahim, K. Ali, Families of regular graphs with constant metric dimension, Utilitas Math., 75 (2008), 21–33.
[16]	I. Javaid, S. Shokat, On the partition dimension of some wheel related graphs, J. Prim. Res. Math., 4 (2008), 154–164.
[17]	M. A. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat., 3 (1993), 203–236. https://doi.org/10.1080/10543409308835060 doi: 10.1080/10543409308835060
[18]	M. A. Johnson, Browsable structure-activity datasets, JAI Press Connecticut, 1998,153–170.
[19]	S. Khuller, B. Raghavachari, S. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70 (1996), 217–229. https://doi.org/10.1016/0166-218X(95)00106-2
[20]	H. R. Lewis, M. R. Garey, D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman and Company, 1979.
[21]	M. C. Monica, S. Santhakumar, Partition dimension of certain honeycomb derived networks, IJPAM, 108 (2016), 809–818. https://doi.org/10.12732/ijpam.v108i4.7 doi: 10.12732/ijpam.v108i4.7
[22]	N. Mehreen, R. Farooq, S. Akhter, On partition dimension of fullerene graphs, AIMS Mathematics, 3 (2018), 343–352. https://doi.org/10.3934/Math.2018.3.343 doi: 10.3934/Math.2018.3.343
[23]	R. A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Vis. Graph. Image Process, 25 (1984), 113–121. https://doi.org/10.1016/0734-189X(84)90051-3 doi: 10.1016/0734-189X(84)90051-3
[24]	B. Rajan, A. William, I. Rajasingh, C. Grigorious, S. Stephen, On certain networks with partition dimension three, Proc. Int. Conf. Math. English Bus. Manage., 2012 (2012), 169–172.
[25]	J. A. Rodríuez-Velázquez, I. G. Yero, M. Lemańska, On the partition dimension of trees, Discrete Appl. Math., 166 (2014), 204–209. https://doi.org/10.1016/j.dam.2013.09.026 doi: 10.1016/j.dam.2013.09.026
[26]	H. Fernau, J. A. Rodríuez-Velázquez, I. G. Yero, On the partition dimension of unicyclic graphs, Bull. Math. Soc. Sci. Math. Roumanie, 57 (2014), 381–391.
[27]	P. J. Slater, Leaves of trees, Congr. Numer., 14 (1975), 549–559.
[28]	P. J. Slater, Dominating and reference sets in graphs, J. Math. Phys., 22 (1988), 445–455.
[29]	I. G. Yero, J. A. Rodríuez-Velázquez, A note on the partition dimension of Cartesian product graphs, Appl. Math. Comput., 22 (1998), 445–455.
[30]	C. Wei, M. F. Nadeem, H. M. A. Siddiqui, M. Azeem, J. B. Liu, A. khalil, On partition dimension of some cycle-related graphs, Math. Probl. Eng., 2021 (2021), 4046909. https://doi.org/10.1155/2021/4046909 doi: 10.1155/2021/4046909
[31]	Z. B. Zheng, A. Ahmad, Z. Hussain, M. Munir, M. I. Qureshi, I. Ali, et al. Fault-tolerant metric dimension of generalized wheels and convex polytopes, Math. Probl. Eng., 2020 (2020), 1216542. https://doi.org/10.1155/2020/1216542 doi: 10.1155/2020/1216542

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)