Pelabelan L(2, 1) pada graf koprima dari grup bilangan bulat modulo m

ABSTRAK

Grup adalah himpunan takkosong yang dilengkapi dengan operasi biner dan memenuhi syarat-syarat tertentu. Salah satu contoh grup yaitu grup bilangan bulat modulo m. Graf koprima dari grup G adalah graf yang simpulnya merupakan elemen di G dan dua simpul x,y di G yang berbeda terhubung langsung jika dan hanya jika faktor persekutuan terbesar (FPB) dari orde x dan y relatif prima. Pelabelan L(2,1) memiliki aplikasi penting dalam jaringan telekomunikasi nirkabel, di mana terdapat keterbatasan frekuensi radio yang tersedia dan transmitter yang berdekatan tidak dapat menggunakan frekuensi yang sama. Untuk mengatasi masalah ini, penetapan frekuensi dilakukan menggunakan konsep pelabelan, di mana transmitter disimbolkan sebagai simpul yang dihubungkan oleh sisi-sisi. Pelabelan L(2,1) adalah teknik pelabelan graf yang memberikan label bilangan bulat non-negatif pada simpul-simpul graf dengan aturan bahwa dua simpul yang terhubung langsung harus memiliki selisih label minimal dua, dan dua simpul yang berjarak dua harus memiliki selisih label minimal satu. Tujuan penelitian ini adalah mengetahui rumus umum pelabelan L(2,1) pada graf koprima dari grup bilangan bulat modulo m dan rumus umum nilai minimal label terbesar dari pelabelan L(2,1) tersebut. Tahapan yang dilakukan dalam penelitian ini adalah menentukan bentuk graf koprima dari grup bilangan bulat modulo m. Kemudian melabeli setiap simpul dengan aturan pelabelan L(2,1). Dari hasil penelitian ini dapat disimpulkan bahwa graf koprima dari grup bilangan bulat modulo m mempunyai pelabelan L(2,1) dengan λ_2,1 ( Γ_(Z_m ) )=2p^2.

ABSTRACT

Groups are nonempty sets equipped with binary operations and fulfill certain conditions. One example of a group is the group of integers modulo m. A coprime graph of a group G is a graph whose vertices are elements in G and any two vertices x,y in G are directly connected if and only if the greatest common factor (GCD) of the orders x and y are relatively prime. L(2,1) labeling has important applications in wireless telecommunication networks, where there are limited radio frequencies available and adjacent transmitters cannot use the same frequency. To overcome this problem, frequency assignment is done using the concept of labeling, where transmitters are symbolized as vertices connected by edges. L(2,1) labeling is a graph labeling technique that assigns non-negative integer labels to graph vertices with the rule that two directly connected vertices must have a minimum label difference of two, and two vertices that are two apart must have a minimum label difference of one. The purpose of this research is to find out the general formula for the L(2,1) labeling on the coprime graph of the group of integers modulo m and the general formula for the minimum value of the largest label of the L(2,1) labeling. The steps taken in this research are to determine the coprime graph form of the group of integers modulo m. Then label each vertex with a non-negative label. Then label each vertex with L(2,1) labeling rule. From the result of this research, it can be concluded that the coprime graph of integer group modulo m has a L(2,1) labeling with λ_2,1 (Γ_(Z_(2p^2 ) ) )=2p^2.

مستخلص البحث

المجموعة عبارة عن مجموعة غير فارغة مجهزة بعمليات ثنائية وتفي بشروط معينة. من إحدى الأمثلة على المجموعة هو مجموعة الأعداد الصحيحة modulo m. الرسم البياني الرئيسي للمجموعة G هو رسم البياني الذي يكون رؤوس العبارة عن العناصر في G ورأسان مختلفان x,y في G مرتبطان مباشرة إذا وفقط إذا كان العامل المشترك الأكبر (FPB) من الرتبة x وy أوليًا نسبيًا. إن وضع العلامات L(2,1) له تطبيقات مهمة في شبكات الاتصالات اللاسلكية، حيث تتوفر ترددات راديو محدودة ولا يمكن لأجهزة الإرسال المجاورة استخدام نفس التردد. للتغلب على هذه المشكلة، يتم تنفيذ تخصيص التردد باستخدام مفهوم التسمية، حيث يتم ترميز أجهزة الإرسال على أنها عقد متصلة بحواف. وضع العلامات L(2,1) عبارة عن تقنية لوضع علامات على الرسم البياني يقوم بتعيين تسميات أعداد صحيحة غير سالبة لرؤوس الرسم البياني مع القاعدة التي تنص على أن القمتين المتصلتين بشكل مباشر يجب أن يكون لهما اختلاف في التسمية لا يقل عن اثنين، ويجب أن يكون للرأسين اللذين يفصل بينهما مسافة مسافتين الحد الأدنى من الفرق التسمية. الهدف من هذا البحث هو معرفة الصيغة العامة للتسمية L(2,1) على الرسوم البيانية الرئيسية لمجموعات الأعداد الصحيحة modulo m والصيغة العامة لأدنى القيمة للتسمية الأكبر من التسمية L(2,1) . المراحل التي تم تنفيذها في هذا البحث هي تحديد شكل الرسم البياني coprime لمجموعة من الأعداد الصحيحة modulo m. ثم قم بتسمية كل عقدة باستخدام قاعدة التسمية L(2,1). من نتائج هذا البحث يمكن استنتاج أن الرسم البياني coprime لمجموعة الأعداد الصحيحة modulo m يملك L(2,1)بـ .λ_2,1 (Γ_(Z_(2p^2 ) ) )=2p^2.