ANALISIS PEWARNAAN r-DINAMIS PADA GRAF-GRAF KHUSUS
Abstract
Pewarnaan graf merupakan salah satu topik kajian pada teori graf. Pe-
warnaan r-dinamis merupakan pengembangan dari pewarnaan k-warna dinamis
yang diperkenalkan oleh Montgomery pada tahun 2002. Pewarnaan k-warna di-
namis pada graf G merupakan pewarnaan titik pada graf G sebanyak k warna
sedemikian hingga setiap titik berderajat minimum dua pada G setidaknya memi-
liki dua warna berbeda dengan titik-titik ketetanggaannya. Nilai k terkecil dimana
graf G memiliki pewarnaan k-warna dinamis disebut sebagai bilangan kromatik
dinamis, disimbolkan dengan Âd(G).
Graf-graf khusus yang digunakan dalam penelitian ini adalah graf Prisma,
graf Circulant, graf Lintasan, graf Sikel, graf Roda, graf Bintang, graf Tangga,
dan graf Friendship. Metode yang digunakan dalam penelitian ini adalah metode
deduktif aksiomatik, yang diawali dengan istilah yang tidak dide¯nisikan dan
istilah yang dide¯nisikan, kemudian dapat disusun pernyataan pangkal yang biasa
disebut aksioma atau postulat. Setelah itu, disusun teorema-teorema ataupun
de¯nisi-de¯nisi. Adapun teorema yang disusun harus dibuktikan melalui proses
deduktif sehingga kebenarannya berlaku secara umum dalam ruang lingkupnya.
Hasil penelitian ini berupa teorema baru mengenai pewarnaan titik r-dinamis
dan pewarnaan sisi r-dinamis pada graf-graf khusus. Teorema yang dihasilkan
adalah:
a. Bilangan kromatik r-dinamis pewarnaan titik r-dinamis pada graf Prisma,
Pn, dapat ditulis sebagai berikut:
Â(Pn) =
(
2; untuk n genap
3; untuk n ganjil
Âd(Pn) =
(
3; untuk n = 3k; k 2 N
4; untuk n lainnya
Âr¸3(Pn) =
8>><
>>:
4; untuk n = 4k; k 2 N
6; untuk n = 3; 7; 11
5; untuk n lainnya
ix
yang telah dibuktikan pada Teorema 4.1.1;
b. Misalkan G merupakan graf Circulant, yakni Cn(1; n
2 ), dimana n ¸ 4 dan
n genap. Bilangan kromatik dinamis pewarnaan titik r-dinamis pada graf
Circulant, Cn(1; n
2 ), dapat ditulis sebagai berikut:
Â(Cn(1;
n
2
)) =
8>><
>>:
4; untuk n = 4
2; untuk n = 4k + 2; k 2 N
3; untuk n = 4k + 4; k 2 N
Âd(Cn(1;
n
2
)) = 4
Âr¸3(Cn(1;
n
2
)) =
8>>>><
>>>>:
n; untuk n = 4; 6; 8
4; untuk n = 8k + 4; k 2 N
5; untuk n = 8k + 6; k 2 N
6; untuk n lainnya
yang telah dibuktikan melalui pembuktian Teorema 4.1.2;
c. Misalkan G merupakan graf Circulant, yakni Cn(1; 2), dimana n ¸ 5. Bi-
langan kromatik dinamis pewarnaan titik r-dinamis pada graf Circulant,
Cn(1; 2), dapat ditulis sebagai berikut:
Â(Cn(1; 2)) = Â2(Cn(1; 2)) =
8>><
>>:
5; untuk n = 5
3; untuk n = 3k; k 2 A
4; untuk n lainnya
Â3(Cn(1; 2)) =
(
4; untuk n = 4k; k 2 A
5; untuk n lainnya
Âr¸4(Cn(1; 2)) =
8>>>><
>>>>:
n; untuk 5 · n · 9
5; untuk n = 5k + 5; k 2 A
6; untuk n = 5k + 6; 5k + 7; k 2 A
7; untuk n = 5k + 8; 5k + 9; k 2 A
yang telah dibuktikan pada Teorema ??;
d. Jika G merupakan graf hasil operasi join antara Pn dan Cm, dinotasikan
dengan Pn + Cm maka bilangan kromatik r-dinamis graf G adalah sebagai
x
berikut:
Â4(Pn + Cm) =
(
5; untuk m = 3k; k 2 A
6; untuk m lainnya
Â5(Pn + Cm) =
8>><
>>:
6; untuk m = 3
8; untuk m = 5
7; untuk m lainnya
Âr¸6(Pn+Cm) =
(
r + m ¡ 2; untuk 3 · m · r ¡ 2;m ¸ r ¡ 1; n ¸ m ¡ 1
2r ¡ 3; untuk m lainnya; n ¸ r ¡ 1
yang telah dibuktikan pada Teorema 4.1.4;
e. Misalkan G merupakan graf hasil operasi korona antara Pn dan Cm, yaitu
Cm ¯ Pn. Jika n ¸ 2, m ¸ 3, and r ¸ 4 maka bilangan kromatik r-dinamis
graf G adalah sebagai berikut:
Âr¸4(Cm ¯ Pn) =
8>>>><
>>>>:
4; untuk m 6= 5; n = 1;
5; untuk n = 2 dan m = 5; n = 1;
n + 3; untuk 3 · n · r ¡ 3;
r + 1; untuk n lainnya;
yang telah dibuktikan pada Teorema 4.1.5;
f. Misalkan G merupakan graf hasil operasi korona antara Pn dan Cm, yaitu
Pn ¯ Cm. Jika n ¸ 2, m ¸ 3, dan r ¸ 6 maka bilangan kromatik r-dinamis
graf G adalah sebagai berikut:
Âr¸6(Pn ¯ Cm) =
(
m + 3; untuk 3 · m · r ¡ 3;
r + 1; untuk m lainnya;
yang telah dibuktikan pada Teorema 4.1.6;
g. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Lintasan,
Pn, dapat ditulis sebagai berikut:
¸(Pn) = 2; n ¸ 2
¸2(Pn) = ¸r(Pn) = 3; n ¸ 2; r ¸ 2
yang telah dibuktikan pada Teorema 4.2.1;
h. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Sikel, Cn; n ¸
3, dapat ditulis sebagai berikut:
¸(Cn) =
(
2; untuk n genap
3; untuk n ganjil
¸r¸2(Cn) =
8>><
>>:
3; untuk n = 3k; k 2 N
4; untuk n = 3k + 1; k 2 N
5; untuk n = 3k + 2; k 2 N
yang telah dibuktikan pada Teorema 4.2.2;
i. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Bintang,
Sn; n ¸ 3, dapat ditulis sebagai berikut:
¸r¸1(Sn) = n
yang telah dibuktikan pada Teorema 4.2.3;
j. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Roda, Wn; n ¸
5, dapat ditulis sebagai berikut:
¸r·n¡1(Wn) = n; untuk 1 · r · n ¡ 1
¸r¸n(Wn) =
8>><
>>:
10; untuk n = 5; r ¸ n
n + 3; untuk untukn = 3k + 3; k 2 N; r ¸ n
n + 4; untuk n lainnya; r ¸ n
yang telah dibuktikan pada Teorema 4.2.4;
k. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Prisma, Pn,
dapat ditulis sebagai berikut:
¸(Pn) = ¸2(Pn) =
(
2; untuk n genap
3; untuk n ganjil
¸3(Pn) =
(
4; untuk n = 3
5; untuk n lainnya
¸r¸4(Pn) =
8>>>><
>>>>:
9; untuk n = 3
6; untuk n = 4k; k 2 N
8; untuk n = 5; 6; 4k + 7; k 2 N
7; untuk n lainnya
yang telah dibuktikan pada Teorema 4.2.5;
l. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Tangga,
Ln; n ¸ 3, adalah:
¸(Ln) = ¸2(Ln) = 3
¸3(Ln) = 5
¸4(Ln) = ¸r(Ln) = 6
yang telah dibuktikan pada Teorema 4.2.6;
h. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Sikel, Cn; n ¸
3, dapat ditulis sebagai berikut:
¸(Cn) =
(
2; untuk n genap
3; untuk n ganjil
¸r¸2(Cn) =
8>><
>>:
3; untuk n = 3k; k 2 N
4; untuk n = 3k + 1; k 2 N
5; untuk n = 3k + 2; k 2 N
yang telah dibuktikan pada Teorema 4.2.2;
m. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Friendship,
Fn, adalah:
¸r·2n¡1(Fn) = 2n
¸r¸2n(Fn) = 2n + 1
yang telah dibuktikan pada Teorema 4.2.7;
n. Misalkan G adalah graf hasil operasi amalgamasi dari graf Lintasan Pn,
dinotasikan G = amal(Pn; v;m); n ¸ 2;m ¸ 3, maka bilangan kromatik sisi
r-dinamis pada graf G adalah:
¸(amal(Pn; v;m)) = ¸2(amal(Pn; v;m)) = m
¸r¸3(amal(Pn; v;m)) = m + 1
yang telah dibuktikan pada Teorema 4.2.8;
o. Jika T adalah graf Pohon, maka berlaku:
Â(Cn + T) = Â2(Cn + T) = Â3(Cn + T) =
(
4; untuk n genap
5; untuk n ganjil
yang telah dibuktikan pada Teorema 4.3.1;
p. Misalkan G adalah graf yang merupakan hasil operasi join graf G1 dan G2,
maka pada graf G berlaku pewarnaan titik r-dinamis sebagai berikut:
Â(G1 + G2) = Â2(G1 + G2) = ¢ ¢ ¢ = Âr(G1 + G2) = Â(G1) + Â(G2)
dimana r = minfjc(N(v(G1)))j; jc(N(v(G2)))jg+minfÂG1 ; ÂG2g, yang telah
dibuktikan pada Teorema 4.3.2;
q. Jika G merupakan graf Pohon maka ¸r(G) = minfr; maxfd(u)+d(v)¡2gg+
1, dimana r ¸ maxfd(u)+d(v)¡2gg, yang telah dibuktikan pada Teorema
4.3.3.
Dari penelitian juga terdapat dugaan mengenai pewarnaan titik r-dinamis
pada graf Pn + Cm sebagaimana tertulis pada Dugaan 4.3.1:
Misalkan G adalah graf yang merupakan hasil operasi join graf G1 dan G2, maka
Âr(G1 + G2) ¸ Âr(G1) + Âr(G2).
Collections
- MT-Mathematic [99]