Dimensi Metrik Lokal pada Graf Garis dari Graf Persahabatan

Fithri Annisatun Lathifah, Universitas Negeri Yogyakarta, Indonesia

Abstract


Diberikan suatu graf terhubung G=(V(G), E(G)) dengan V(G) adalah himpunan titik dan E(G) adalah himpunan sisi di G. Misalkan W={w_1, w_2, ..., w_k} subhimpunan terurut tak kosong dari V(G). Untuk sebarang titik v di G, representasi titik v terhadap W yang dinotasikan r(v|W) didefinisikan sebagai k-vektor (d_G(v,w_1), d_G(v,w_2), ..., d_G(v,w_k)) dengan d_G(v,w_i) adalah panjang lintasan v-w_i terpendek untuk i=1,2, ..., k. Bilangan kardinal k dari W yang minimum sehingga untuk setiap dua titik yang bertetangga di G memiliki representasi yang berbeda disebut sebagai dimensi metrik lokal dari G, dinotasikan dengan lmd(G). Graf garis L(G) dari graf G adalah graf yang dikonstruksi dengan mengambil semua sisi di G sebagai titik-titik pada L(G), dan dua titik pada L(G) bertetangga jika kedua sisi pada G yang bersesuaian dengan kedua titik tersebut mempunyai titik bersama. Graf persahabatan F_n dengan 2n+1 titik adalah graf yang diperoleh dengan menggabungkan n salin C_3 dengan satu titik bersama. Dalam artikel ini diperoleh bahwa dimensi metrik lokal pada graf garis dari graf persahabatan adalah lmd(L(F_n))=2n-1.

Kata kunci: dimensi metrik lokal, graf garis, graf persahabatan.


References


Cahyabudi, A. N. & Kusmayadi, T. A. (2017). On the local metric dimension of a lollipop graph, a web graph, and a friendship graph. J. Phys.: Conf. Ser. 909 012039. https://doi.org/10.1088/1742-6596/909/1/012039

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

Feng, M., Xu, M. & Wang, K. (2013). On the metric dimension of line graphs. Discrete Applied Mathematics, 161, 802-805. https://doi.org/10.1016/j.dam.2012.10.018

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

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

Okamoto, F., Crosse, L., Phinezy, B., Zhang, P. & Kalamazoo (2010). The local metric dimension of a graph. Mathematica Bohemica, 3, 239-255. http://dx.doi.org/10.21136/MB.2010.140702

Pitoy, C. R. (2018). Dimensi Metrik Lokal dari Graf Sirkulan, Tesis Program Magister. Institut Teknologi Bandung.

Rodríguez-Velázquez, J.A., Barragán-Ramírez, G.A. & García Gómez, C. (2016). On the Local Metric Dimension of Corona Product Graphs. Bull. Malays. Math. Sci. Soc. 39 (Suppl 1), 157–173. https://doi.org/10.1007/s40840-015-0283-1

Rodríguez-Velázquez, J. A., García Gómez, C., & Barragán-Ramírez, G. A. (2015). Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs. International Journal of Computer Mathematics, 92(4), 686–693. https://doi.org/10.1080/00207160.2014.918608

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

Slater, P. J. (1975). Leaves of trees. Proceedings 6th Southeastern Conference on Combinatorics, Graph Theory and Computing, 14, 549-559.


Refbacks

  • There are currently no refbacks.


 


Online ISSN (e-ISSN): 3031-1152

Creative Commons LicenseJurnal Kajian dan Terapan Matematika by https://journal.student.uny.ac.id/index.php/jktm/index is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.