SACS | On Sharp Bounds of Fault-Tolerant Partition Dimension of Convex Polytopes

Published in Volume XXXV, Issue 2, 2025, pages 139–160, doi:10.47743/SACS.2025.2.139

Author: K. Azhar, A. Nadeem, Y. Shang

Abstract

Graph theory is a fundamental and powerful tool for designing and modeling networks. It plays a vital role in diverse real-world systems, including social, computer, biological, ecological, and neural networks. Convex polytopes are convex sets of elements contained in the Euclidean space ℝⁿ. They arise in numerous domains such as linear programming, finance, computer science, electrical engineering, bioinformatics, and chemistry. From the graph-theoretic perspective, some sharp upper bounds for the partition dimension of convex polytopes have been established recently. Inspired by this, in this paper, we aim to investigate the fault-tolerant partition dimension (FTPD), which is an extension of the partition dimension. Here, we compute bounds for the FTPD of certain convex polytopes. These results contribute to a deeper understanding of the robustness of network structures modeled by convex polytopes and may support further applications in fault-tolerant system design.

Full Text (PDF)

References

[1] Imtiaz Ali, Muhammad Javaid, and Yilun Shang. Computing dominant metric dimensions of certain connected networks. Heliyon, 10(4):e25654, 2024. doi:10.1016/j.heliyon.2024.e25654.

[2] Kamran Azhar, Sohail Zafar, Agha Kashif, Amer Aljaedi, and Umar Albalawi. Fault-tolerant partition resolvability in mesh related networks and applications. IEEE Access, 10:71521–71529, 2022. doi:10.1109/ACCESS.2022.3188319.

[3] Kamran Azhar, Sohail Zafar, Agha Kashif, and Michael Onyango Ojiema. Fault-tolerant partition resolvability of cyclic networks. Journal of Mathematics, 2021(1):7237168, 2021. doi:10.1155/2021/7237168.

[4] Kamran Azhar, Sohail Zafar, Agha Kashif, and Zohaib Zahid. On fault-tolerant partition dimension of graphs. Journal of Intelligent & Fuzzy Systems, 40(1):1129–1135, 2021. doi:10.3233/JIFS-201390.

[5] Kamran Azhar, Sohail Zafar, Agha Kashif, and Zohaib Zahid. Fault- tolerant partition resolvability in chemical graphs. Polycyclic Aromatic Compounds, 43(10):8830–8840, 2023. doi:10406638.2022.2156559.

[6] Kamran Azhar, Sohail Zafar, Asim Nadeem, and Yilun Shang. Fault- tolerant partition resolvability of cycle with chord. PLOS ONE, 19(11):1– 11, 2024. doi:10.1371/journal.pone.0313300.

[7] Ludovic Cales, Apostolos Chalkis, Ioannis Z. Emiris, and Vissarion Fisikopoulos. Practical Volume Computation of Structured Convex Bodies, and an Application to Modeling Portfolio Dependencies and Financial Crises. In Bettina Speckmann and Csaba D. Toth, editors, 34th International Symposium on Computational Geometry (SoCG 2018), volume 99 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:15, 2018. doi:10.4230/LIPIcs.SoCG.2018.19.

[8] Gary Chartrand, Ebrahim Salehi, and Ping Zhang. The partition dimension of a graph. Aequationes Mathematicae, 59:45–54, 2000. doi:10.1007/PL00000127.

[9] Yu-Ming Chu, Muhammad Faisal Nadeem, Muhammad Azeem, and Muhammad Kamran Siddiqui. On sharp bounds on partition dimension of convex polytopes. IEEE Access, 8:224781–224790, 2020. doi:10.1109/ACCESS.2020.3044498.

[10] Branko Grunbaum. Convex polytopes. In Volker Kaibel, Victor Klee, and Gunter M. Ziegler, editors, Graduate Texts in Mathematics, volume 221. Springer, 2nd edition, 2003. doi:10.1007/978-1-4613-0019-9.

[11] Hulda S Haraldsdottir, Ben Cousins, Ines Thiele, Ronan M.T Fleming, and Santosh Vempala. CHRR: coordinate hit-and-run with rounding for uniform sampling of constraint-based models. Bioinformatics, 33(11):1741–1743, 2017. doi:10.1093/bioinformatics/btx052.

[12] Frank Harary and Robert A. Melter. On the metric dimension of a graph. Ars Combinatoria, 2:191–195, 1976.

[13] Carmen Hernando, Merce Mora, Peter J Slater, and David R. Wood. Fault-tolerant metric dimension of graphs. In Manoj Changat, Sandi Klavzar, Henry Martyn Mulder, and A. Vijayakumar, editors, Joint Proceedings of the International Instructional Workshop on Convexity in Discrete Structures,Thiruvananthapuram, India, 2006 and the International Workshop on Metric and Convex Graph Theory, Barcelona, Spain, 2006, volume 5 of Lecture Notes Series, pages 81–85. Ramanujan Mathematical Society, 2008.

[14] Zafar Hussain, Junaid Alam Khan, Mobeen Munir, Muhammad Shoaib Saleem, and Zaffar Iqbal. Sharp bounds for partition dimension of generalized M¨obius ladders. Open Mathematics, 16(1):1283–1290, 2018. doi:10.1515/math-2018-0109.

[15] Muhammad Imran, Fozia Bashir, A. Baig, Syed Bokhary, Haq Bokhary, Ayesha Riasat, and Ioan Tomescu. On metric dimension of flower graph fn×m and convex polytopes. Utilitas Mathematica, 92:389–409, 2013.

[16] Muhammad Imran, Syed Bokhary, and A. Baig. On the metric dimension of rotationally-symmetric convex polytopes. Journal of Algebra Combinatorics Discrete Structures and Applications, 3:45–59, 2016. doi:10.13069/jacodesmath.47485.

[17] Muhammad Imran and Hafiz Muhammad Afzal Siddiqui. Computing the metric dimension of convex polytopes generated by wheel related graphs. Acta Mathematica Hungarica, 149:10–30, 2016. doi:10.1007/s10474-016-0606-1.

[18] Imran Javaid and Sara Shokat. On the partition dimension of some wheel related graphs. Journal of Prime Research in Mathematics, 4:154–164, 2008.

[19] Samir Khuller, Balaji Raghavachari, and Azriel Rosenfeld. Localization in graphs. Technical Report CS-TR-3326, University of Maryland at College Park, 1994.

[20] Samir Khuller, Balaji Raghavachari, and Azriel Rosenfeld. Landmarks in graphs. Discrete Applied Mathematics, 70(3):217–229, 1996. doi:10.1016/0166-218X(95)00106-2.

[21] Asim Nadeem, Agha Kashif Arshad Khan, Sohail Zafar, and Zohaib Zahid. On 2–partition dimension of rotationally-symmetric graphs. Discrete Mathematics, Algorithms and Applications, 15:2250153, 2022. doi:10.1142/S1793830922501531.

[22] Asim Nadeem, Kamran Azhar, Agha Kashif Arshad Khan, and Sohail Zafar. On the partition dimension of circulant graph C_n(1,2,3,4). Punjab University Journal of Mathematics, 55(3):117–133, 2023. doi:10.52280/pujm.2023.550303.

[23] Asim Nadeem, Agha Kashif, Ebenezer Bonyah, and Sohail Zafar. Fault tolerant partition resolvability in convex polytopes. Mathematical Problems in Engineering, 2022(1):3238293, 2022. doi:10.1155/2022/3238293.

[24] Asim Nadeem, Agha Kashif, Sohail Zafar, Amer Aljaedi, and Oluwatobi Akanbi. Fault tolerant addressing scheme for oxide interconnection networks. Symmetry, 14(8):1740, 2022. doi:10.3390/sym14081740.

[25] Afsaneh Rezaei, Kazem Khashyarmanesh, and Mojgan Afkhami. On the metric dimension of Cayley graphs. AKCE International Journal of Graphs and Combinatorics, 19(2):118–124, 2022. doi:10.1080/09728600.2022.2077675.

[26] Laxman Saha, Bapan Das, Kalishankar Tiwary, Kinkar Chandra Das, and Yilun Shang. Optimal multi-level fault-tolerant resolving sets of circulant graph c(n : 1, 2). Mathematics, 11(8):1896, 2023. doi:10.3390/math11081896.

[27] Laxman Saha, Rupen Lama, Kalishankar Tiwary, Kinkar Chandra Das, and Yilun Shang. Fault-tolerant metric dimension of circulant graphs. Mathematics, 10(1):124, 2022. doi:10.3390/math10010124.

[28] Muhammad Salman, Imran Javaid, and Muhammad Chaudhry. Fault- tolerant metric and partition dimension of graphs. Utilitas Mathematica, 83:187–199, 2010.

[29] Muhammad Salman, Imran Javaid, Muhammad Chaudhry, and Sara Shokat. Fault-tolerance in resolvability. Utilitas Mathematica, 80:263– 275, 2009.

[30] Yilun Shang. Subspace confinement for switched linear systems. Forum Mathematicum, 29(3):693–699, 2017. doi:10.1515/forum-2015-0188.

[31] Peter J. Slater. Leaves of trees. In Proceeding of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing, volume 14 of Congressus Numerantium, pages 549–559. 1975.

Bibtex

@article{sacscuza:Shang25osbftpdcp, 
	    title={On Sharp Bounds of Fault-Tolerant Partition Dimension of Convex Polytopes}, 
	    author={K. Azhar, A. Nadeem, Y. Shang},
	    journal={Scientific Annals of Computer Science}, 
	    volume={35},
	    number={2}, 
	    organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania}, 
	    year={2025}, 
	    pages={139-160},
	    publisher={Alexandru Ioan Cuza University Press, Ia\c si},
	    doi={10.47743/SACS.2025.2.139} 
	    }