Login Register Cart 0
Generic placeholder image

Combinatorial Chemistry & High Throughput Screening

Editor-in-Chief

ISSN (Print): 1386-2073
ISSN (Online): 1875-5402

Back
Journal Home About Journal Editorial Board Journal Insight Current Issue Volumes/Issues
Subscribe
Research Article

Bounds on the Partition Dimension of Convex Polytopes

Author(s): Jia-Bao Liu, Muhammad Faisal Nadeem* and Mohammad Azeem

Volume 25, Issue 3, 2022

Published on: 04 December, 2020

Page: [547 - 553] Pages: 7

DOI: 10.2174/1386207323666201204144422

Price: $65

Abstract

Aims and Objective: The idea of partition and resolving sets play an important role in various areas of engineering, chemistry and computer science such as robot navigation, facility location, pharmaceutical chemistry, combinatorial optimization, networking, and mastermind game.

Methods: In a graph, to obtain the exact location of a required vertex, which is unique from all the vertices, several vertices are selected; this is called resolving set, and its generalization is called resolving partition, where selected vertices are in the form of subsets. A minimum number of partitions of the vertices into sets is called partition dimension.

Results: It was proved that determining the partition dimension of a graph is a nondeterministic polynomial time (NP) problem. In this article, we find the partition dimension of convex polytopes and provide their bounds.

Conclusion: The major contribution of this article is that due to the complexity of computing the exact partition dimension, we provide the bounds and show that all the graphs discussed in the results have partition dimensions either less or equals to 4, but not greater than 4.

Keywords: Partition dimension, resolving partition, resolving sets, convex polytopes, bounded partition dimension.

« Previous Next »
Graphical Abstract

[1]
Slater, P.J. Leaves of trees. Congr. Numer., 1975, 14, 549-559.
[2]
Harary, F.; Melter, R.A. On the metric dimension of a graph. Ars Comb., 1976, 2, 191-195.
[3]
Khuller, S.; Raghavachari, B.; Rosenfeld, S. Landmarks in graphs. Discrete Appl. Math., 1996, 70(3), 217-229.
[http://dx.doi.org/10.1016/0166-218X(95)00106-2]
[4]
Chartrand, G.; Eroh, L.; Johnson, M.A.; Oellermann, O.R. Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math., 2000, 105(1-3), 99-113.
[http://dx.doi.org/10.1016/S0166-218X(00)00198-0]
[5]
Söderberg, S.; Shapiro, H.S. A combinatory detection problem. Am. Math. Mon., 1963, 70(10), 1066-1070.
[http://dx.doi.org/10.1080/00029890.1963.11992174]
[6]
Manuel, P.; Bharati, R.; Rajasingh, I.; Monica, C.M. On minimum metric dimension of honeycomb networks. J. Discrete Algorithms, 2008, 6(1), 20-27.
[http://dx.doi.org/10.1016/j.jda.2006.09.002]
[7]
Sebö, A.; Tannier, E. On metric generators of graphs. Math. Oper. Res., 2004, 29(2), 383-393.
[http://dx.doi.org/10.1287/moor.1030.0070]
[8]
Perc, M.; Szolnoki, A. Coevolutionary games--a mini review. Biosystems, 2010, 99(2), 109-125.
[http://dx.doi.org/10.1016/j.biosystems.2009.10.003] [PMID: 19837129]
[9]
Chartrand, G.; Salehi, E.; Zhang, P. The partition dimension of graph. Aequ. Math., 2000, 59, 45-54.
[http://dx.doi.org/10.1007/PL00000127]
[10]
Garey, M.R.; Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness; Freeman: New York, 1979.
[11]
Mohan, C.M.; Santhakumar, S.; Arockiaraj, M.; Liu, J-B. Partition dimension of certain classes of series parallel graphs. Theor. Comput. Sci., 2019, 778, 47-60.
[http://dx.doi.org/10.1016/j.tcs.2019.01.026]
[12]
Rajan, B.; William, A.; Rajasingh, I.; Grigorious, C.; Stephen, S. On certain networks with partition dimension three Proceedings of the International Conference on Mathematics in Engineering and Business Management, 2012, 169-172.
[13]
Monica, M.C.; Santhakumar, S. Partition dimension of certain honeycomb derived networks. Int. J. Pure Appl. Math., 2016, 108(4), 809-818.
[http://dx.doi.org/10.12732/ijpam.v108i4.7]
[14]
Javaid, I.; Shokat, S. On the partition dimension of some wheel related graphs. J. Prime Res. Math., 2008, 4, 154-164.
[15]
Rodrluez-Velàzquez, J.A.; Yero, I.G.; Fernau, H. On the partition dimension of unicyclic graphs. B. Math. Soc. Sci. Math., 2014, 57, 381-391.
[16]
Baskoro, E.T.; Haryeni, D.O. All graphs of order n ≥ 11 and diameter 2 with partition dimension n - 3. Heliyon, 2020, 6(4)e03694
[http://dx.doi.org/10.1016/j.heliyon.2020.e03694] [PMID: 32322708]
[17]
Vertana, H.; Kusmayadi, T.A. On The partition dimension of Cm+ Pn graph. J. Phys. Conf. Ser., 2016, 855.
[18]
Hussain, Z.; Kang, S.M.; Rafique, M.; Munir, M.; Ali, U.; Zahid, A.; Saleem, M.S. Bounds for partition dimension of M-wheels. Open Phys., 2019, 16.
[19]
Mehreen, N.; Farooq, R.; Akhter, S. On partition dimension of fullerene graphs. AIMS Mathematics, 2018, 3(3), 343-352.
[http://dx.doi.org/10.3934/Math.2018.3.343]
[20]
Grigorious, C.; Stephen, S.; Rajan, B.; Miller, M. On the partition dimension of circulant Graphs. Comput. J., 2017, 60(2), 180-184.
[21]
Maritz, E.C.M.; Vetrík, T. The partition dimension of circulant graphs. Quaest. Math., 2018, 41(1), 49-63.
[http://dx.doi.org/10.2989/16073606.2017.1370031]
[22]
Safriadi, S.; Hasmawati, H.; Haryanto, L. Partition Dimension of Complete Multipartite Graph. J. Matematika, Statistika dan Komputasi., 2020, 16(3)
[23]
Kuziak, D.; Yero, I. G. Further new results on strong resolving partitions for graphs. Open Mathematics., 2020, 05-14.
[http://dx.doi.org/10.1515/math-2020-0142]
[24]
Rehman, T.U.; Mehreen, N. Partition Dimension and Strong Metric Dimension of Chain Cycle. Jordan J. Math. Stats, 2020, 13(2), 305-325.
[25]
Alfarisi, R.; Kristiana, A.I. Dafik. The local partition dimension of graphs. Discrete Math. Algorithms Appl., 2020, 13(3)2150028
[http://dx.doi.org/10.1142/S1793830921500282]
[26]
Moreno, E. On the k-partition dimension of graphs. Theor. Comput. Sci., 2020, 806, 42-52.
[http://dx.doi.org/10.1016/j.tcs.2018.09.022]
[27]
Haryeni, D.O.; Baskoro, E.T.; Saputro, S.W.; Baca, M.; Fenovcikova, A.S. On the partition dimension of two-component graphs. Proc. Math. Sci., 2017, 127(5), 755-767.
[http://dx.doi.org/10.1007/s12044-017-0363-2]
[28]
Imran, M.; Bokhary, S.A.U.H.; Baig, A.Q. On families of convex polytopes with constant metric dimension. Comput. Math. Appl., 2010, 60(9), 2629-2638.
[http://dx.doi.org/10.1016/j.camwa.2010.08.090]
[29]
Baca, M. On magic labellings of convex polytopes. Ann. Discrete Math., 1992, 1992(51), 13-16.
[http://dx.doi.org/10.1016/S0167-5060(08)70599-5]
[30]
Imran, M.; Ul Haq Bokhary, S.A.; Baig, A.Q. On the metric dimension of rotationally-symmetric convex polytopes. J. Algebra Comb. Discret. Appl., 2015, 3, 45-59.

Rights & Permissions Print Cite
Article Metrics
13
1
© 2024 Bentham Science Publishers | Privacy Policy