Bilangan Kromatik Lokasi Graf Amal(K_n, K_m)
Keywords:
Kelas Warna, Kode Warna, Pewarnaan Lokasi, Bilangan Kromatik LokasiAbstract
Misalkan G adalah pasangan terurut (V, E), yaitu graf terhubung, dan c adalah suatu pemetaan warna pada graf G yang didefinisikan sebagai c dari V(G) ke himpunan {1, 2, ..., t}, dengan t adalah bilangan asli. Jika simpul u dan v bertetangga di G, maka c(u) tidak sama dengan c(v). Misalkan S_h adalah himpunan simpul yang diberi warna h untuk setiap h anggota {1, 2, ..., t}, maka S_h disebut kelas warna. Misalkan Pi adalah partisi dari himpunan simpul V(G) yaitu Pi = {S_1, S_2, ..., S_t} untuk suatu pewarnaan.
Kode warna c_Pi dari simpul v dalam G didefinisikan sebagai vektor dengan t komponen yaitu c_Pi(v) = (d(v, S_1), d(v, S_2), ..., d(v, S_t)), di mana d(v, S_h) adalah jarak minimum antara v dan setiap simpul x dalam S_h, yaitu d(v, S_h) = minimum dari d(v, x) untuk x dalam S_h, dan h dari 1 sampai t.
Jika setiap simpul dalam G memiliki kode warna yang berbeda untuk suatu partisi Pi, maka pewarnaan c disebut sebagai pewarnaan lokasi. Nilai minimum dari t sedemikian sehingga G memiliki pewarnaan lokasi dengan t warna disebut sebagai bilangan kromatik lokasi, dan dinotasikan dengan chi sub L dari G.
Dalam penelitian ini dibahas tentang bilangan kromatik lokasi dari graf Amal(K_n, K_m). Graf Amal(K_n, K_m) adalah graf yang dibentuk dengan menggabungkan satu simpul di setiap graf lengkap K_n ke setiap simpul di graf lengkap K_m secara satu-satu, dengan syarat m dan n lebih besar atau sama dengan 2, dan m serta n adalah bilangan asli.
Dengan menentukan batas bawah dan batas atas bilangan kromatik lokasi, diperoleh bahwa bilangan kromatik lokasi dari graf Amal(K_n, K_m) adalah:
-
sebesar n + 1 jika m lebih kecil atau sama dengan n, dan
-
sebesar m jika m lebih besar dari n
Downloads
References
U. S. R. M. Bondy, J.A., Graph Theory. New York, 2008.
P. Z. Gary Chartrand, David Erwin, Michael A. Henning, Peter J. Slater, “The Locating-Chromatic Number of a Graph,” Bull. ICA, vol. 36, pp. 89–101, 2002.
G. Chartrand, L. Lesniak, and P. Zhang, Graphs & Digraphs, Sixth Edition. 2016. [Online]. Available: https://books.google.com/books?hl=nl&lr=&id=K6-FvXRlKsQC&pgis=1
G. Chartrand, D. Erwin, M. A. Henning, P. J. Slater, and P. Zhang, “Graphs of order n with locating-chromatic number n - 1,” Discrete Math., vol. 269, no. 1–3, pp. 65–79, 2003, doi: 10.1016/S0012-365X(02)00829-4.
D. Welyyanti, E. T. Baskoro, R. Simanjuntak, and S. Uttunggadewa, “On locating-chromatic number of complete n-ary tree,” AKCE Int. J. Graphs Comb., vol. 10, no. 3, pp. 309–315, 2013.
D. Welyyanti, E. T. Baskoro, R. Simanjuntak, and S. Uttunggadewa, “The locating-chromatic number of disconnected graphs,” Far East J. Math. Sci., vol. 94, no. 2, pp. 169–182, 2014.
M. Behtoei, A., Anbarloei, “The locating chromatic number of the join of graphs,” Bull. Iran. Math. Soc., vol. 40, no. 6, pp. 1491–1504, 2014.
A. Asmiati, L. Yulianti, and C. I. T. Widyastuti, “Further Results on Locating Chromatic Number for Amalgamation of Stars Linking by One Path,” Indones. J. Comb., vol. 2, no. 1, p. 50, 2018, doi: 10.19184/ijc.2018.2.1.6.
Asmiati, I. K. Sadha Gunce Yana, and L. Yulianti, “On the Locating Chromatic Number of Certain Barbell Graphs,” Int. J. Math. Math. Sci., vol. 2018, pp. 1–6, 2018, doi: 10.1155/2018/5327504.
N. Andriani, “Bilangan Kromatik Lokasi Pada Graf Amalgamasi Kipas Berekor,” Limits J. Math. Its Appl., vol. 20, no. 1, p. 81, 2023, doi: 10.12962/limits.v20i1.12948.
T. Utomo and N. Riskiana Dewi, “Dimensi Metrik Graf Amal(nKm),” Limits J. Math. Its Appl., vol. 15, no. 1, p. 71, 2018, doi: 10.12962/limits.v15i1.3376.
A. W. Bustan, A. N. M. Salman, and P. E. Putri, “On the locating rainbow connection number of amalgamation of complete graphs,” J. Phys. Conf. Ser., vol. 2543, no. 1, pp. 1–6, 2023, doi: 10.1088/1742-6596/2543/1/012004.
