Metric Dimension of Banded-Turán Graph

Muhammad Nurul Huda, Department of Mathematics, Universitas Gadjah Mada, Yogyakarta, Indonesia
Hartono Hartono, Department of Mathematics Education, Universitas Negeri Yogyakarta, Yogyakarta, Indonesia

Abstract


Given a graph G=(V(G),E(G)). Let S={s1,...,sk} be an ordered subset of V(G). Consider a vertex x, a coordinate of x with respect to S is represented as r(x|S)=(d(x,s1),...,d(x,sk)) where d(x,si) equals the number of edges in the shortest path between x and si for i=1,...,k. The minimum value of k such that for every x has distinct coordinate is called metric dimension of G. Turán graph T(n,r), n>=r>=2  is a subgraph of complete r-partite graph on n vertices having property that the difference of cardinality of any two distinct classes is at most one. In this paper, we build a new graph namely a banded-Turán graph, BT(n,r,m), as a graph built by a Turán graph T(n,r) and r uniform path graphs Pm in which every vertex of each class of T(n,r) connected to an initial vertex of corresponding path graph Pm. Intuitively, this graph illustrates as if a Turán graph is banded by r uniform ropes. We determine some basic graph properties including independence number, chromatic number, and diameter of banded-Turán. The main result in this paper is we obtain that the metric dimension of banded-Turán turns out that it depends on the number of its classes. If it has two classes then the metric dimension is equal to n-1 and if it has more than two classes then the metric dimension is equal to the metric dimension of Turán graph included in it.

Keywords


Metric dimension; path graph; Turán graph

Full Text:

PDF

References


Adrianto, F. A., Permanasari, Y., Sukarsih, I. (2015). Penerapan Pewarnaan Graf sebagai Metode untuk Mencari Solusi Permainan Sudoku. Prosiding Penelitian SPeSIA Unisba, 17-23. https://karyailmiah.unisba.ac.id/index.php/matematika/article/view/1731

Aigner, M. (1995). Turán’s Graph Theorem, The American Mathematical Monthly, 808-815.

Akhter, S., Farooq, R. (2019). Metric dimension of fullerene graphs, Electronic Journal of Graph Theory and Applications, 7 (1), 91-103. https://dx.doi.org/10.5614/ejgta.2019.7.1.7

Alexanderson, G. L. (2006). About The Cover: Euler and Königsberg’s Bridges: A Historical View, Bulletin of the American Mathematical Society, 43 no. 4, 567-573. http://dx.doi.org/10.1090/S0273-0979-06-01130-X

AlHoli, M. M., AbuGhneim, O. A., Al-Ezeh, H. (2017). Metric Dimension of Some Path Related Graphs, Global Journal of Pure and Applied Mathematics, 149-157. https://doi.org/10.1155/2021/2085778

Basudeb, M., Kajal, D. (2017). Overview Applications of Graph Theory in Real Field, International Journal of Scientific Research in Computer Science, Engineering and Information Technology, 2, 751-759. https://ijsrcseit.com/home/issue/view/article.php?id=CSEIT1725170

Bollobás, B., Mitsche, D., Pralat, P. (2013). Metric dimension for random graphs, The Electronic Journal of Combinatorics, 1-19. https://doi.org/10.37236/2639

Cáceres, J., Garijo, D., Puertas M.L., Seara C. (2010). On determining number and metric dimension of graphs, Electronic Journal of Combinatorics, 17 (1). https://doi.org/10.37236/335

Chartrand, G., Eroh, L., Johnson, M.A., Oellermann, O.R. (2000). Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105, 99-113. https://doi.org/10.1016/S0166-218X(00)00198-0

Dolzan, D. (2016). The Metric Dimension of the Total Graph of A Finite Commutative Ring, Canad. Math. Bull., 59 (4), 748-759. https://doi.org/10.4153/CMB-2016-015-5

Fehr, M., Gosselin, S., Oellermann, O. R. (2006). The metric dimension of Cayley digraphs, Discrete Math., 306, 31-41. https://doi.org/10.1016/j.disc.2005.09.015

Gross, J. L., Yellen, J., Anderson, M. (2019). Graph Theory and Its Applications, CRC Press Taylor & Francis Group, Boca Raton. https://doi.org/10.1201/9780429425134

Harary, F., & Melter, R. A. (1976). On the metric dimension of a graph, Ars Combin, 2, 191-195.

Imran, M., Baig, A. Q., Bokhary, S. A. U. H., Javaid, I. (2012). On the metric dimension of circulant graphs, Applied Mathematics Letters, 25, 320-325. https://doi.org/10.1016/j.aml.2011.09.008

Iswadi, H., Baskoro, E. T., Simanjuntak, R. (2011). On the Metric Dimension of Corona Product of Graphs, Far East Journal of Mathematical Sciences (FJMS), 155-170. https://www.pphmj.com/abstract/5882.htm

Khuller, S., Raghavachari, B., Rosenfeld, A. (1994). Localization in Graphs, Technical Report CS-TR-3326, University of Maryland at College Park.

Khuller, S., Raghavachari, B., Rosenfeld, A. (1996). Landmarks in graphs, Discrete Appl. Math., 70, 217-229. https://doi.org/10.1016/0166-218X(95)00106-2

Melter, R. A., Tomescu, I. (1984). Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing, 25, 113-121. https://doi.org/10.1016/0734-189X(84)90051-3

Mutianingsih, N. (2016). Dimensi Metrik Pada Graf Turán, WAHANA: Jurnal Ilmiah Sains & Ilmu Pendidikan, 67. https://doi.org/10.36456/wahana.v67i2.500

Rahman, M. S. (2017). Basic Graph Theory, Springer Nature, Switzerland.

Rehman, S. u., Imran, M., Javaid, I. (2020). On the Metric Dimension of Arithmetric Graph of A Composite Number, Symmetry, 12 (4). https://doi.org/10.3390/sym12040607

Rosen, K. H. (2012). Discrete Mathematics and its Applications, McGraw-Hill, New York.

Saputro, S. W., Baskoro, E. T., Salman, A. N. M., Suprijanto, D. (2009). The metric dimension of a complete n-partite graph and its cartesian product with a path, J. Combin. Math. Combin. Comput., 71, 283-293. https://www.researchgate.net/publication/268624519_The_metric_dimensions_of_a_complete_n-partite_graph_and_its_Cartesian_product_with_a_path

Saputro, S. W., Baskoro, E. T., Salman, A. N. M., Suprijanto, D., Baca, M. (2011). The metric dimension of regular bipartite graphs, Bull. Math. Soc. Sci. Math. Roumanie Tome, 54 (102), 15-28. https://www.researchgate.net/profile/Djoko-Suprijanto/publication/257201731_BBSSS-2011/links/00b7d524a4205c8a7d000000/BBSSS-2011.pdf

Shao, Z., Sheikholeslami, S. M., Wu, P., Liu, J. B. (2018). The Metric Dimension of Some Generalized Petersen Graphs, Hindawi: Discrete Dynamics in Nature and Society.

Slater. PJ. (1975). Leaves of trees, Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, 14 of Congr. Numer, 549-559.

Slater. PJ. (1988). Dominating and reference sets in a graph, J. Math. Phys. Sci. 22, 445-455.

Sebő, A., Tannier, E. (2004). On Metric Generators of Graphs, Mathematics of Operations Research, 29 (2), 383-393. https://doi.org/10.1287/moor.1030.0070

Zhang, X., Naeem, M. (2021). Metric Dimension of Crystal Cubic Carbon Structure, Hindawi: Journal of Mathematics. https://doi.org/10.1155/2021/3438611




DOI: https://doi.org/10.21831/pythagoras.v19i1.68025

Refbacks

  • There are currently no refbacks.


PYTHAGORAS: Jurnal Matematika dan Pendidikan Matematika indexed by:


Creative Commons License Pythagoras is licensed under a Creative Commons Attribution 4.0 International License.
Based on a work at http://journal.uny.ac.id/index.php/pythagoras.

All rights reserved p-ISSN: 1978-4538 | e-ISSN: 2527-421X

Visitor Number:

View Pythagoras Stats