Dimensi Metrik pada Graf Bintang Kipas dan Graf Bunga Sepatu
DOI:
https://doi.org/10.12962/limits.v22i2.3455Keywords:
metric dimension, resolving set, basis, fan star graph, hibiscus graphAbstract
Let be a connected graph with set of vertices and set of edges . The distance from two distinct vertices , denoted by , is the length of the shortest path from and in . Let be an ordered subset of . For any vertex , the representation of vertex with respect to is defined as k-ordered pairs . The set is said to be the resolving set of if every two vertices differ then . The basis of is the resolving set of with the smallest cardinality. The cardinality of the base is defined as metric dimension, and is denoted by . This research aims to find the metric dimension of fan star graph and hibiscus graph. The research method in this research is a literature study. The result of this research are as follow the metric dimension of the fan star graph are for and and for dan , then the metric dimension of the hibiscus gaph are for and for .
Downloads
References
G. Chartrand and L. Lesniak, Graphs & Digraphs, 3rd ed., vol. 33, no. 4. Chapman & Hall/CRC, USA, 1996. doi: 10.1016/s0898-1221(97)90011-0.
P. J. Slater, “Leave of Trees,” Congr. Numer., vol. 14, pp. 549–559, 1975.
F. Harary and R. A. Melter, “On the Metric Dimension of a Graph,” Ars Comb. 2, pp. 191–195, 1976.
G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann, “Resolvability in Graphs and the Metric Dimension of a Graph,” Discret. Appl. Math., vol. 105, no. 1–3, pp. 99–113, 2000, doi: 10.1016/S0166-218X(00)00198-0.
P. Buczkowski, G. Chartrand, C. Poisson, and P. Zhang, “On k-Dimensional Graphs and Their Bases,” Period. Math. Hungarica, vol. 46, no. 1, pp. 9–15, 2003, doi: https://doi.org/10.1023/a:1025745406160.
S. A. Wijaya and T. A. Kusmayadi, “On the Metric Dimension of Amalgamation of Sunflower and Lollipop Graph and Caveman Graph,” J. Phys. Conf. Ser., vol. 1306, no. 1, 2019, doi: 10.1088/1742-6596/1306/1/012035.
M. Sabila and T. A. Kusmayadi, “On the Metric Dimension of Generalized Broken Fan Graph and Edge Corona Product of Path with Star Graph,” J. Phys. Conf. Ser., vol. 1306, no. 1, 2019, doi: 10.1088/1742-6596/1306/1/012017.
P. D. Sari and T. A. Kusmayadi, “Dimensi Metrik Pada Graf Starbarbell dan Hasil Operasi Edge Corona Pada Graf Cycle dan Graf Path,” J. Mat., vol. 10, no. 1, pp. 32–43, 2020, doi: 10.24843/jmat.2020.v10.i01.p121.
M. R. Garey and D. S. Johnson, Computers and Intractibility: A Guide to The Theory of NP Completeness, 1st ed. W.H. Freeman and Company, 1979. [Online]. Available: https://perso.limos.fr/~palafour/PAPERS/PDF/Garey-Johnson79.pdf
S. Khuller, B. Raghavachari, and A. Rosenfeld, “‘Landmarks in graphs,’” Discret. Appl. Math., vol. 70, no. 3, pp. 217–229, 1996, doi: 10.1016/0166-218X(95)00106-2.
P. D. Manuel, M. I. Abd-El-Barr, I. Rajasingh, and B. Rajan, “An Efficient Representation of Benes Networks and Its Applications,” J. Discret. Algorithms, vol. 6, no. 1, pp. 11–19, 2008, doi: 10.1016/j.jda.2006.08.003.
J. Diaz, O. Pottonen, M. Serna, and E. J. Van Leeuwen, “On the Complexity of Metric Dimension,” Proc. ESA 2010 LNCS, vol. 7501, no. 1, pp. 419–430, 2012, doi: https://doi.org/10.1007/978-3-642-33090-237.
A. W. Bustan and A. N. M. Salman, “The Rainbow Vertex-Connection Number of Star Fan Graphs,” CAUCHY J. Mat. Murni dan Apl., vol. 5, no. 3, pp. 112–116, 2018, doi: 10.18860/ca.v5i3.5516.
F. Alyani and H. Jusra, “Pelabelan Harmonis Ganjil Pada Graf Diamond dan Graf Bunga Sepatu (Laporan Penelitian Dasar Keilmuan),” Univ. Muhammadiyah Prof. Dr. Hamka, p. 10, 2019, [Online]. Available: https://simakip.uhamka.ac.id/publication/collections/penelitianinternal/detail/1024/pelabelan-harmonis-ganjil-pada-graf
