BILANGAN KROMATIK GRAF COMMUTING DAN NONCOMMUTING  
GRUP DIHEDRAL 

1Handrini Rahayuningtyas, 2Abdussakir, 3Achmad Nashichuddin 

1Jurusan Matematika, Universitas Islam Negeri Maulana Malik Ibrahim Malang 
2jurusan Matematika, Universitas Islam Negeri Maulana Malik Ibrahim Malang 
3jurusan Matematika, Universitas Islam Negeri Maulana Malik Ibrahim Malang 

 
Email: handrienie05@gmail.com 

ABSTRAK 
Graf commuting adalah graf yang memiliki himpunan titik X dan dua titik berbeda akan terhubung 

langsung jika saling komutatif di 𝐺. Misal 𝐺 grup non abelian dan 𝑍(𝐺) adalah center dari 𝐺. Graf 
noncommuting adalah suatu graf yang mana titik-titiknya merupakan himpunan dari 𝐺\𝑍(𝐺) dan dua titik 
x dan y terhubung langsung jika dan hanya jika 𝑥𝑦 ≠ 𝑦𝑥. Pewarnaan titik pada graf 𝐺 adalah pemberian 
sebanyak k warna pada titik sehingga dua titik yang terhubung langsung tidak diberi warna yang sama. 
Pewarnaan sisi pada graf 𝐺 adalah dua sisi yang berasal dari titik yang sama diberi warna yang berbeda. 
Bilangan terkecil k sehingga suatu graf dapat diberi k warna pada titik dan sisi inilah yang dinamakan 
bilangan kromatik. Pada artikel ini didapatkan rumus umum bilangan kromatik dari graf commuting dan 
noncommuting yang dibangun dari suatu grup yaitu grup dihedral.  

Kata kunci: bilangan kromatik, pewarnaan titik, pewarnaan sisi, graf commuting dan noncommuting,  
grup dihedral. 

ABSTRACT 
Commuting graph is a graph that has a set of points X and two different vertices to be connected 

directly if each commutative in 𝐺. Let 𝐺 non abelian group and 𝑍(𝐺) is a center of 𝐺. Noncommuting graph 
is a graph which the the vertex is a set of 𝐺\𝑍(𝐺) and two vertices x and y are adjacent if and only if 𝑥𝑦 ≠
𝑦𝑥. The vertex colouring of 𝐺 is giving k colour at the vertex, two vertices that are adjacent not given the 
same colour. Edge colouring of G is two edges that have common vertex are coloured with different colour. 
The smallest number k so that a graph can be coloured by assigning 𝑘 colours to the vertex and edge 
called chromatic number. In this article, it is available the general formula of chromatic number of 
commuting and noncommuting graph of dihedral group. 

Keywords: chromatic number, vertex colouring, edge colouring, commuting and noncommuting graph, 
dihedral group. 

 
PENDAHULUAN   

Graf G adalah pasangan (𝑉(𝐺), 𝐸(𝐺)) 
dengan 𝑉(𝐺) adalah himpunan tidak kosong dan 
berhingga dari objek-objek yang disebut titik, dan 
𝐸(𝐺) adalah himpunan (mungkin kosong) 
pasangan tak berurutan dari titik-titik berbeda di 
𝑉(𝐺) yang disebut sisi. Banyaknya unsur di 𝑉(𝐺) 
disebut order dari G dan dilambangkan dengan 
𝑝(𝐺), dan banyaknya unsur di 𝐸(𝐺) disebut 
ukuran dari G dan dilambangkan dengan 𝑞(𝐺). Jika 
graf yang dibicarakan hanya graf 𝐺, maka order 
dan ukuran dari 𝐺 masing-masing cukup ditulis 𝑝 
dan 𝑞. Graf dengan order 𝑝 dan ukuran 𝑞 dapat 
disebut graf (𝑝, 𝑞) [1]. 

Sisi e = (u,v) dikatakan menghubungkan 
titik u dan v. Jika e = (u,v) adalah sisi di graf G, 
maka u dan v disebut terhubung langsung 
(adjacent), v dan e serta u dan e disebut terkait 
langsung (incident), dan titik u dan v disebut ujung 
dari e. Dua sisi berbeda e1 dan e2 disebut 

terhubung langsung (adjacent), jika terkait 
langsung pada satu titik yang sama. Untuk 
selanjutnya, sisi e = (u, v) akan ditulis e = uv [2]. 

Perkembangan terbaru teori graf yaitu 
membahas graf yang dibangun oleh suatu grup. 
Misal 𝐺 grup berhingga dan 𝑋 adalah subset dari 
𝐺. Graf commuting 𝐶(𝐺, 𝑋) adalah graf yang 
memiliki himpunan titik 𝑋 dan dua titik berbeda 
akan terhubung langsung jika saling komutatif di 
𝐺. Jadi, titik x dan y akan terhubung langsung di 
𝐶(𝐺, 𝑋) jika dan hanya jika 𝑥𝑦 =  𝑦𝑥 di 𝐺 (Vahidi 
& Talebi, 2010:123). Sebaliknya, Misal 𝐺 grup non 
abelian dan 𝑍(𝐺) adalah center dari 𝐺. Graf 
noncommuting Γ𝐺  adalah suatu graf yang mana 
titik-titiknya merupakan himpunan dari 𝐺\𝑍(𝐺) 
dan dua titik 𝑥 dan 𝑦 terhubung langsung jika dan 
hanya jika 𝑥𝑦 ≠ 𝑦𝑥 [3]. 

Perkembangan berikutnya muncul bilangan 
kromatik pewarnaan titik dan pewarnaan sisi 
pada graf. Pewarnaan titik pada graf 𝐺 adalah 
pemberian sebanyak 𝑛 warna pada titik sehingga 

mailto:handrienie05@gmail.com


Handrini Rahayuningtyas 

 

17  Volume 4 No.1 November 2015 
 

dua titik yang saling terhubung langsung tidak 
diberi warna yang sama. Pewarnaan sisi pada graf 
𝐺 adalah pemberian sebanyak 𝑛 warna pada sisi 
sehingga dua sisi yang saling terkait langsung 
tidak diberi warna yang sama. Bilangan 𝑛 terkecil 
sehingga graf 𝐺 dapat diwarnai dengan cara 
tersebut dinamakan bilangan kromatik. Bilangan 
kromatik titik ditulis 𝜒(𝐺) dan  bilangan kromatik 
sisi ditulis 𝜒′(𝐺) [1]. 

KAJIAN TEORI 

1. Graf 𝑮 

Graf G adalah pasangan (V(G), E(G)) dengan 
V(G) adalah himpunan tidak kosong dan berhingga 
dari objek-objek yang disebut titik, dan E(G) 
adalah himpunan (mungkin kosong) pasangan 
takberurutan dari titik-titik berbeda di V(G) yang 
disebut sisi [1].  

Sehingga jika 𝐺 = (𝑉(𝐺), 𝐸(𝐺)), maka 

𝑉(𝐺) = {𝑣1, 𝑣2, … , 𝑣𝑛 } dan 𝐸(𝐺) = {𝑒1, 𝑒2, … , 𝑒𝑛 }, 
dimana 𝑣𝑖 ∈ 𝑉(𝐺), 𝑖 = 1,2, … , 𝑛 disebut titik 
(vertex) dan 𝑒𝑗 = 1,2, … , 𝑚 disebut sisi (edge). 

 
2. Derajat Titik 

Jika v adalah titik pada graf 𝐺, maka 
himpunan semua titik di 𝐺 yang terhubung 
langsung dengan 𝑣 disebut lingkungan dari v dan 
ditulis 𝑁𝐺(𝑣). Derajat dari titik 𝒗 di graf 𝐺, ditulis 
deg𝐺 (𝑣), adalah banyaknya sisi di 𝐺 yang terkait 
langsung dengan v.  Derajat total G adalah jumlah 
derajat semua titik dalam G. Dalam konteks 
pembicaraan hanya terdapat satu graf G, maka 
tulisan deg𝐺 (𝑣) disingkat menjadi deg(v) dan 
NG(v) disingkat menjadi N(v). Jika dikaitkan 
dengan konsep lingkungan, derajat titik v di graf G 
adalah banyaknya anggota dalam N(v) [2].  

 
Gambar 1. Graf 𝑮 dengan Himpunan 

Titik 𝑽(𝑮) 
Berdasarkan gambar, diperoleh bahwa:  

𝑁(𝑎) = {𝑏, 𝑐, 𝑑} 
𝑁(𝑏) = {𝑎, 𝑐} 
𝑁(𝑐) = {𝑎, 𝑏, 𝑑} 
𝑁(𝑑) = {𝑎, 𝑐}. 

Dengan demikian, maka  
deg(𝑎) = 3 

deg(𝑏) = 2 
deg(𝑐) = 3 
deg(𝑑) = 2 

 

3. Graf Terhubung 

Suatu graf G dikatakan terhubung jika 
untuk setiap titik u dan v di G terdapat lintasan u-v 
di G. Sebaliknya, jika ada dua titik u dan v di G, 
tetapi tidak ada lintasan u-v di G, maka G 
dikatakan tak terhubung (disconnected) [2]. 

 

4. Bilangan Kromatik 

Pewarnaan titik pada graf G adalah 
pemberian sebanyak n warna pada titik sehingga 
dua titik yang saling terhubung langsung tidak 
diberi warna yang sama. Pewarnaan sisi pada graf 
G adalah pemberian sebanyak n warna pada sisi 
sehingga dua sisi yang saling terkait langsung 
tidak diberi warna yang sama. Bilangan n terkecil 
sehingga graf G dapat diwarnai dengan cara 
tersebut dinamakan bilangan kromatik. Bilangan 
kromatik titik ditulis 𝜒(𝐺) dan  bilangan kromatik 
sisi ditulis 𝜒′(𝐺) [1]. 

 
5. Grup Dihedral 

Grup adalah suatu struktur aljabar yang 
dinyatakan sebagai (𝐺,∗) dengan 𝐺 adalah 
himpunan tak kosong  dan ∗ adalah operasi biner 
di 𝐺 yang memenuhi sifat-sifat berikut:   

1. (𝑎 ∗ 𝑏) ∗= 𝑎 ∗ (𝑏 ∗ 𝑐), untuk semua 𝑎, 𝑏, 𝑐 ∈ 𝐺  
(yaitu assosiatif ). 

2. Ada suatu elemen 𝑒 di 𝐺 sehingga 𝑎 ∗ 𝑒 = 𝑒 ∗
𝑎 = 𝑎, untuk semua 𝑎 ∈ 𝐺 (𝑒 disebut identitas 
di 𝐺). 

3. Untuk setiap 𝑎 ∈ 𝐺 ada suatu element 𝑎−1 di 𝐺 
sehingga 𝑎 ∗ 𝑎−1 = 𝑎−1 ∗ 𝑎 = 𝑒 (𝑎−1 disebut 
invers dari 𝑎)  

Adapun grup (𝐺,∗) disebut abelian (grup 
komutatif) jika 𝑎 ∗ 𝑏 = 𝑏 ∗ 𝑎 untuk semua 𝑎, 𝑏 ∈ 𝐺 
[4]. 

Grup dihedral adalah grup dari himpunan 
simetri-simetri dari segi-n beraturan, 
dinotasikan𝐷2𝑛, untuk setiap 𝑛 bilangan bulat 
positif dan 𝑛 ≥ 3. Dalam buku lain ada yang 
menuliskan grup dihedral dengan 𝐷𝑛 [5]. 

Adapun himpunan anggota grup dihedral 
𝐷2𝑛 yaitu 𝐷2𝑛 = {1, 𝑟, 𝑟

2, … , 𝑠, 𝑠𝑟, 𝑠𝑟2, … , 𝑠𝑟𝑛−1}. 

 
6. Graf Commuting dan Noncommuting 

Misal 𝐺 adalah grup berhingga dan 𝑋 adalah 
subset dari 𝐺, graf commuting 𝐶(𝐺, 𝑋) adalah graf 
dengan 𝑋 sebagai himpunan titik dan dua elemen 
berbeda di 𝐶(𝐺, 𝑋) terhubung langsung jika 



Bilangan Kromatik Graf Commuting dan Noncommuting Grup Dihedral 

 
 

CAUCHY – ISSN: 2086-0382/E-ISSN: 2477-3344 18   
 
 

keduanya adalah elemen yang saling komutatif di 
𝐺 [6]. 

Misal 𝐺 grup non abelian dan 𝑍(𝐺) adalah 
center dari 𝐺. Graf non commuting Γ𝐺  adalah suatu 
graf yang mana titik-titiknya merupakan 
himpunan dari 𝐺\𝑍(𝐺) dan dua titik 𝑥 dan 𝑦 
terhubung langsung jika dan hanya jika 𝑥𝑦 ≠ 𝑦𝑥 
[3]. 

PEMBAHASAN 

Pewarnaan titik pada graf G adalah 
pemberian sebanyak n warna pada titik sehingga 
dua titik yang saling terhubung langsung tidak 
diberi warna yang sama. Pewarnaan sisi pada graf 
G adalah pemberian sebanyak n warna pada sisi 
sehingga dua sisi yang saling terkait langsung 
tidak diberi warna yang sama. Dari pewarnaan 
titik dan sisi inilah dapat diketahui bilangan 
kromatiknya, baik graf commuting maupun graf 
noncommuting.  

 
Bilangan Kromatik Pewarnaan Titik dan Sisi 
Graf Commuting Grup Dihedral 

Perhatikan tabel di bawah ini: 

Tabel 1. Bilangan Kromatik Pewarnaan Titik dan 
Sisi Graf Commuting Grup Dihedral 

𝐶(𝐷2𝑛 ) 𝜒(𝐶(𝐷2𝑛 )) 𝜒
′(𝐶(𝐷2𝑛 )) 

𝐷6 3 5 

𝐷8 4 7 

𝐷10 

.

.

.
 

5 

.

.

.
 

9 

.

.

.
 

𝐷2𝑛 𝑛 2𝑛 − 1 

Sumber: penulis 
Berdasarkan Tabel 1, didapatkan teorema 

berikut: 

 
Teorema 1 

Misal 𝐶(𝐷2𝑛 ) adalah graf commuting dari 
grup dihedral-2n (𝐷2𝑛 ). Maka bilangan kromatik 
pewarnaan titik graf commuting dari grup 

dihedral-2n (𝐷2𝑛 ) adalah 𝜒(𝐶(𝐷2𝑛 )) = 𝑛. 

Bukti: 
Untuk 𝑛 ganjil dan genap, misal diketahui 𝑣 =
{1, 𝑟, 𝑟2, … , 𝑟𝑛−1} di 𝐷2𝑛, untuk 𝑖 ≠ 𝑗. Kemudian 
𝑟𝑖 ∘ 𝑟𝑗 = 𝑟𝑗 ∘ 𝑟𝑖  untuk 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 di 𝐷2𝑛, 

maka 𝑟𝑖  dan 𝑟𝑗  saling terhubung langsung di 
𝐶(𝐷2𝑛 ). Karena 𝑟

𝑖  dan 𝑟𝑗  saling komutatif, maka 
terdapat (𝑟𝑖 , 𝑟𝑗 ) ∈ 𝐶(𝐷2𝑛 ) yang membentuk 
subgraf komplit-𝑛. Sehingga dibutuhkan sebanyak 
𝑛 warna, atau dengan kata lain bilangan kromatik 
pewarnaan titik 𝑟𝑖  dan 𝑟𝑗  yaitu 𝑛.  
Misal 𝑤 = {𝑠, 𝑠𝑟, 𝑠𝑟1, … , 𝑠𝑟𝑛−1} dimana 𝑤 hanya 
komutatif dengan 1 di 𝐷2𝑛. Artinya 𝑠𝑟

𝑖  dan 
𝑠𝑟𝑗 , 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 tidak saling komutatif. 
Karena tidak saling komutatif, maka dapat diberi 
warna yang sama.  
Pada 𝑛 ganjil, 𝑠𝑟𝑖  tidak komutatif dengan 𝑟𝑗 , 𝑗 =
1,2, … , 𝑛 − 1. 

𝑠𝑟 ∘ 𝑟 = 𝑠𝑟1+1 
       = 𝑠𝑟2 

𝑟 ∘ 𝑠𝑟 = 𝑠𝑟1−1 
   = 𝑠 

Karena 𝑠𝑟𝑖  tidak komutatif dengan 𝑟𝑗, 𝑗 =
1,2, … , 𝑛 − 1, maka warna titik 𝑠𝑟𝑖  berlaku sama 
dengan titik 𝑟𝑗 , 𝑗 = 1,2, … , 𝑛 − 1. 

Pada 𝑛 genap, terdapat 𝑠𝑟
𝑛

2 ∘ 𝑟
𝑛

2 = 𝑟
𝑛

2 ∘ 𝑠𝑟
𝑛

2 , 

sehingga warna titik 𝑠𝑟
𝑛

2  tidak boleh sama dengan 

𝑟
𝑛

2 . Selain itu, terdapat 𝑠𝑟
𝑛

2 ∘ 𝑟𝑖 = 𝑟𝑖 ∘ 𝑠𝑟
𝑛

2 , sehingga 

warna titik 𝑠𝑟
𝑛

2  boleh sama dengan warna titik 𝑟𝑖 , 
atau dengan kata lain 𝑠𝑟𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1 dapat 

diberi warna yaitu memilih dari 
𝑛

2
 warna. Jadi, 

diperoleh 𝜒(𝐶(𝐷2𝑛 )) = 𝑛, untuk 𝑛 ganjil maupun 

genap.  
 
Teorema 2 

Misal 𝐶(𝐷2𝑛 ) adalah graf commuting dari grup 
dihedral-2n (𝐷2𝑛 ). Maka bilangan kromatik 
pewarnaan sisi graf commuting dari grup dihedral-
2n (𝐷2𝑛 ) adalah 𝜒′(𝐶(𝐷2𝑛 )) = 2𝑛 − 1 

 
Bukti: 
Untuk 𝑛 ganjil, diketahui bahwa 𝑟𝑖 ∘ 𝑟𝑗 = 𝑟𝑗 ∘ 𝑟𝑖 , 
untuk 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 di 𝐷2𝑛, untuk 𝑖 ≠ 𝑗. Jadi, 
𝑟𝑖  dan 𝑟𝑗  saling terhubung langsung di 𝐺. Di 
samping itu, 1 komutatif dengan semua elemen 𝑟𝑖  
dan 𝑠𝑟𝑖 , sehingga 1 terhubung langsung dengan 
semua elemen 𝑟𝑖  dan 𝑠𝑟𝑖, 𝑖 = 0,1,2, … , 𝑛 − 1 di 𝐺. 
Karena 1 terhubung langsung dengan 2𝑛 − 1 
elemen di 𝐺, maka minimal warna yang digunakan 
pewarnaan sisinya yaitu sebanyak 2𝑛 − 1 warna. 
Berdasarkan aturan pewarnaannya, setiap sisi 
yang terkait dengan 1 titik yang sama diberi 
warna yang berbeda. Adapun 𝑟𝑖  dan 𝑟𝑗 , 𝑖 =
0,1,2, … ,2𝑛 − 1 yang saling terhubung langsung 
dapat diberi warna dari 2𝑛 − 1 warna yang telah 
digunakan sebelumnya. Sehingga didapatkan 
bilangan kromatik sisinya yaitu 𝜒′(𝐶(𝐷2𝑛 )) =

2𝑛 − 1, untuk 𝑛 ganjil. 
Untuk 𝑛 genap, diketahui bahwa  Untuk 𝑛 ganjil, 
diketahui bahwa 𝑟𝑖 ∘ 𝑟𝑗 = 𝑟𝑗 ∘ 𝑟𝑖 , untuk 𝑖, 𝑗 =
0,1,2, … , 𝑛 − 1 di 𝐷2𝑛, untuk 𝑖 ≠ 𝑗. Jadi, 𝑟

𝑖  dan 𝑟𝑗  

saling terhubung langsung di 𝐺. Walaupun 𝑟
𝑛

2  



Handrini Rahayuningtyas 

 

19  Volume 4 No.1 November 2015 
 

komutatif dengan 𝑠𝑟𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1, tetapi 
𝑠𝑟𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1 tidak komutatif dengan 𝑟𝑗  

untuk 𝑗 selain 
𝑛

2
. Elemen 1 komutatif dengan 𝑟𝑖  dan 

𝑠𝑟𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1 yaitu sebanyak 2𝑛 − 1 
elemen. Karena 1 komutatif dengan semua elemen 
𝑟𝑖  dan 𝑠𝑟𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1 yaitu sebanyak 2𝑛 −
1 elemen, maka 1 memiliki derajat tertinggi di 𝐺. 
Artinya, minimal warna yang dibutuhkan adalah 
sebesar derajat tertinggi di 𝐺 yaitu 1. 1 terhubung 
langsung dengan 2𝑛 − 1 elemen, maka minimal 
warna yang digunakan dalam pewarnaan sisi di 𝐺 
sebanyak 2𝑛 − 1 warna. Jadi, diperoleh bilangan 

kromatik sisinya yaitu 𝜒′(𝐶(𝐷2𝑛 )) = 2𝑛 − 1, untuk 

𝑛 genap. 
 
Bilangan Kromatik Pewarnaan Titik dan Sisi 
Graf Noncommuting Grup Dihedral 

 
Perhatikan tabel berikut: 
 
Tabel 2. Bilangan Kromatik Graf Noncommuting 
Graf Noncommuting Grup Dihedral 

Γ(𝐷2𝑛 ) 𝜒(Γ(𝐷2𝑛 )) 𝜒
′(Γ(𝐷2𝑛 )) 

Γ(𝐷6) 4 5 

Γ(𝐷8) 3 5 

Γ(𝐷10) 6 9 

Γ(𝐷12) 4 9 

Γ(𝐷14) 8 13 

Γ(𝐷16) 
.
.
.
 

5 
.
.
.
 

13 
.
.
.
 

Γ(𝐷2𝑛 ) 
𝑛 + 1, 𝑛 ganjil 

𝑛

2
+ 1, 𝑛 genap 

2𝑛 − 1, n ganjil 

2𝑛 − 3, n genap 

Sumber: penulis 
Berdasarkan Tabel 2, diperoleh teorema sebagai 
berikut: 
 
Teorema 3 

Misal Γ(𝐷2𝑛 ) adalah graf noncommuting dari grup 
dihedral-2n (𝐷2𝑛 ), maka bilangan kromatik dari 
pewarnaan titik graf noncommuting pada grup 

dihedral-2n (𝐷2𝑛 ) adalah 𝜒(Γ(𝐷2𝑛 )) = 𝑛 + 1 

untuk 𝑛 ganjil dan 𝜒(Γ(𝐷2𝑛 )) =
𝑛

2
+ 1 untuk 𝑛 

genap.  
 
Bukti: 
Untuk 𝑛 ganjil, diperoleh himpunan 𝑆 =
{𝑟, 𝑠, 𝑠𝑟, … , 𝑠𝑟𝑛−1} saling tidak komutatif di 𝐷2𝑛, 
untuk 𝑖 ≠ 𝑗. Dapat dikatakan bahwa 𝑟𝑖  dan 𝑠𝑟𝑗 , 
untuk 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 saling terhubung 

langsung. Dengan demikian, 𝑆 = {𝑟, 𝑠, 𝑠𝑟, … , 𝑠𝑟𝑛−1} 
akan membentuk subgraf komplit terbesar di 𝐺. 
Karena 𝑆 = {𝑟, 𝑠, 𝑠𝑟, … , 𝑠𝑟𝑛−1} membentuk subgraf 
terbesar di 𝐺, maka bilangan clique atau order 
subgraf komplit terbesar graf 𝐺 adalah 𝑛 + 1, yaitu 
kardinalitas himpunan 𝑆. Karena order dari 
subgraf komplit terbesarnya adalah 𝑛 + 1, maka 
pewarnaan titik pada graf 𝐺 membutuhkan 
minimal warna sebanyak 𝑛 + 1 warna. Dengan 
demikian didapatkan bilangan kromatik titik pada 
graf noncommuting grup dihedral yaitu 

𝜒(Γ(𝐷2𝑛 )) = 𝑛 + 1, untuk 𝑛 ganjil.  

Untuk 𝑛 genap, diketahui bahwa 𝑍(𝐺) = {1, 𝑟
𝑛

2 }. 

Karena 𝑟𝑖  dan 𝑠𝑟𝑗 , untuk 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 tidak 
saling komutatif, maka 𝑟𝑖  dan 𝑠𝑟𝑗 , untuk 𝑖, 𝑗 =
0,1,2, … , 𝑛 − 1 terhubung langsung di 𝐺, untuk 𝑖 ≠

𝑗. Karena 𝑠𝑟𝑖 , 𝑖 = 0,1,2, … ,
𝑛

2
 saling komutatif 

dengan 𝑠𝑟𝑗 , 𝑗 =
𝑛

2
,

𝑛

2
+ 1,

𝑛

2
+ 2, … , 𝑛 − 1, maka 𝑠𝑟𝑖  

tidak terhubung langsung dengan 𝑠𝑟𝑗 . Namun 

demikian, 𝑠𝑟𝑖 , 𝑖 = 0,1,2, … ,
𝑛

2
 tidak komutatif satu 

sama lain. Maka 𝑠𝑟𝑖 , 𝑖 = 0,1,2, … ,
𝑛

2
 akan 

membentuk subgraf komplit. Karena 𝑠𝑟𝑖, 𝑖 =

0,1,2, … ,
𝑛

2
  terhubung langsung dengan 𝑟, maka 

diperoleh subgraf komplit terbesar yang memuat 
𝑛

2
+ 1 titik. Dengan kata lain, bilangan clique atau 

order subgraf komplit terbesar graf 𝐺 adalah 
𝑛

2
+

1. Karena order dari subgraf komplit terbesar 𝐺 

adalah 
𝑛

2
+ 1, maka pewarnaan titik pada graf 𝐺 

membutuhkan minimal warna sebanyak 
𝑛

2
+ 1 

warna. Dengan demikian, dapat disimpulkan 
bahwa bilangan kromatik titik graf noncommuting 

grup dihedral yaitu 𝜒(Γ(𝐷2𝑛 )) =
𝑛

2
+ 1, untuk 𝑛 

genap.  
 
Teorema 4 

Misal Γ(𝐷2𝑛 ) adalah graf noncommuting dari grup 
dihedral-2n (𝐷2𝑛 ), maka bilangan kromatik dari 
pewarnaan sisi graf noncommuting pada grup 
dihedral-2𝑛 (𝐷2𝑛 ) adalah 𝜒

′(Γ(𝐷2𝑛 )) = 2𝑛 − 1 

untuk 𝑛 ganjil dan 𝜒′(Γ(𝐷2𝑛 )) = 2𝑛 − 3 untuk 𝑛 

genap. 
 
 
Bukti: 
Untuk 𝑛 ganjil, diketahui 𝑟𝑖  dan 𝑠𝑟𝑗 , 𝑖, 𝑗 =
0,1,2, … , 𝑛 − 1 tidak komutatif, artinya  𝑟𝑖  dan 
𝑠𝑟𝑗 , 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 saling terhubung 
langsung di 𝐷2𝑛, untuk 𝑖 ≠ 𝑗. Karena 𝑟

𝑖  dan 𝑠𝑟𝑗  
saling terhubung langsung, maka membentuk 
subgraf komplit di Γ(𝐷2𝑛). Misal 𝑣 merupakan titik 
di Γ(𝐷2𝑛). Diketahui bahwa banyaknya titik 
berderajat ganjil pada sebuah graf adalah genap, 
dapat ditulis ∑ 𝑑𝑒𝑔(𝑣) = 2𝑛𝑣∈Γ(𝐷2𝑛) . Pada graf 

noncommuting, pada 𝑛 ganjil banyaknya 



Bilangan Kromatik Graf Commuting dan Noncommuting Grup Dihedral 

 
 

CAUCHY – ISSN: 2086-0382/E-ISSN: 2477-3344 20   
 
 

∑(𝑍(𝐷2𝑛 )) adalah 1. Karena pada graf 

noncommuting center grup tidak dimunculkan, 
maka dapat ditulis 

𝐷(Γ(𝐷2𝑛 )) = ∑ deg(𝑣)

𝑣∈Γ(𝐷2𝑛)

− ∑(𝑍(𝐷2𝑛 ))

= 2𝑛 − 1. 
Dengan demikian, minimum warna yang 
digunakan yaitu 2𝑛 − 1. Sehingga didapatkan 
(Γ(𝐷2𝑛 )) = 2𝑛 − 1 untuk 𝑛 ganjil.  

Untuk 𝑛 genap, diketahui  𝑟𝑖  dan 𝑠𝑟𝑗, 𝑖, 𝑗 =
0,1,2, … , 𝑛 − 1 tidak saling komutatif, maka  𝑟𝑖  dan 
𝑠𝑟𝑗 , 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 terhubung langsung di 
Γ(𝐷2𝑛 ), 𝑖 ≠ 𝑗. Diketahui bahwa banyaknya derajat 
titik pada sebuah graf adalah dua kali banyak sisi. 
Misal 𝑣 merupakan titik di Γ(𝐷2𝑛 ), maka dapat 
ditulis ∑ 𝑑𝑒𝑔(𝑣) = 2𝑛𝑣∈Γ(𝐷2𝑛) . Diketahui pada graf 

noncommuting 𝑍(𝐷2𝑛 ) = {1, 𝑟
𝑛

2 }, maka 

∑(𝑍(𝐷2𝑛 )) = 2. Dari banyaknya titik dan center 

grup di Γ(𝐷2𝑛 ), dapat dikatakan 𝐷(Γ(𝐷2𝑛 )) =

2𝑛 − 2. Karena 𝑠𝑟𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1 saling 

komutatif dengan  𝑠𝑟𝑗 , 𝑗 =
𝑛

2
,

𝑛

2
+ 1,

𝑛

2
+ 2, … , 𝑛 − 1, 

maka 𝑠𝑟𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1  tidak terhubung 

langsung dengan 𝑠𝑟𝑗, 𝑗 =
𝑛

2
,

𝑛

2
+ 1,

𝑛

2
+ 2, … , 𝑛 − 1, 

sehingga 𝐷(Γ(𝐷2𝑛 )) = 2𝑛 − 3. Karena 

𝐷(Γ(𝐷2𝑛 )) = |𝑁(𝑣 ∈ 𝐷2𝑛 )| yaitu 2𝑛 − 3, maka 

dapat dikatakan minimal  warna yang digunakan 
sebanyak 2𝑛 − 3 warna. Dengan demikian 
(Γ(𝐷2𝑛 )) = 2𝑛 − 3 untuk 𝑛 genap. 

 
KESIMPULAN 

Berdasarkan pembahasan pada penelitian ini, 
maka dapat diambil kesimpulan mengenai 
bilangan kromatik graf commuting dan 
noncommuting dari grup dihedral yaitu sebagai 
berikut: 

1. Bilangan kromatik dari pewarnaan titik graf 
commuting grup dihedral yaitu 
𝜒(𝐶(𝐷2𝑛 )) = 𝑛, untuk 𝑛 ganjil dan genap. 

2. Bilangan kromatik dari pewarnaan sisi graf 
commuting grup dihedral ialah 
𝜒′(C(𝐷2𝑛 )) = 2𝑛 − 1, untuk 𝑛 ganjil dan 

genap. 
3. Bilangan kromatik dari pewarnaan titik graf 

noncommuting grup dihedral ialah:  

𝜒(Γ(𝐷2𝑛 )) = {
𝑛 + 1, 𝑛 𝑔𝑎𝑛𝑗𝑖𝑙 
𝑛

2
+ 1, 𝑛 𝑔𝑒𝑛𝑎𝑝 

 

4. Bilangan kromatik dari pewarnaan sisi graf 
noncommuting grup dihedral ialah: 

𝜒′(Γ(𝐷2𝑛 )) = {
2𝑛 − 1, 𝑛 𝑔𝑎𝑛𝑗𝑖𝑙
2𝑛 − 3, 𝑛 𝑔𝑒𝑛𝑎𝑝

 

 
 
 

DAFTAR PUSTAKA 

[1]  G. Chartrand and L. Lesniak, Graph and 
Digraph 2nd Edition, California: 
Wadsworth, Inc, 1986.  

[2]  Abdussakir, N. Azizah and F. Novandika, 
Teori Graf, Malang: UIN Malang Press, 
2009.  

[3]  A. Abdollahi, S. Akbari and H. Maimani, 
"Noncommuting Graph of a Group," Journal 
of Algebra, pp. 468-492, 2006.  

[4]  M. Raisinghania and R. Aggrawal, Modern 
Algebra, New Delhi: S. Chand & Company 
Ltd, 1980.  

[5]  D. Dummit and R. Foote, Abstract Algebra, 
New Jersey: Prentice Hall, Inc, 1991.  

[6]  A. Nawawi and Preeley, On Commuting 
Graphs for Element of Order 3 in Symetry 
Groups, Manchester: The Mims Secretary, 
2012.  

[7]  A. G. Parlos, "Linearization Of Nonlinear 
Dynamics," 2014. [Online]. Available: 
http://parlos.tamu.edu/MEEN651/Lineari
zation.pdf. [Accessed 17 Agustus 2014]. 

[8]  R. C. Robinson, An Introduction Dynamical 
System Continuous and Discrete, New 
Jersey: Pearson Education, 2004.  

[9]  W. E. Boyce and R. C. DiPrima, Elementary 
Differential Equations and Boundary Value 
Problems, New York: John Wiley & Sons, 
Inc, 2009.  

[10]  R. O. Kwofie, "A mathematical model of a 
suspension bridge – case study: Adomi 
bridge, Atimpoku, Ghana," Global Advanced 
Research Journal of Engineering, 
Technology, and Innovation, vol. 1(3), pp. 
047-062, 2012.  

[11]  G. Vries, T. Hillen, M. Lewis, J. Müller and M. 
Schönfisch, A Course in Mathematical 
Biology: Quantitative Modeling with 
Mathematical and Computational Methods, 
Alberta: SIAM, 2006.  

[12]  M. Bulmer and J. Eccleston, Photocopier 
Reliability Modeling Using Evolutianary 
Algorithm., John Wiley & Sons, 2003.  

[13]  P. Bhattacharya and R. Bhattacharjee, "A 
Study on Weibull Distribution for 
Estimating the Parameters," Journal of 
Applied Quantitative Methods, vol. 2, p. 5, 
2010.  

[14]  I. P. Kinasih, "Penaksiran Parameter 
Distribusi Weibull Bivariat Menggunakan 
Algoritma Genetika," Tesis, 2012.  

[15]  R. d. S. D. Bartle, Introduction to Real 
Analysis, 3rd edition, New York: JohnWiley, 



Handrini Rahayuningtyas 

 

21  Volume 4 No.1 November 2015 
 

2000.  

[16]  J. D. T. L. Lindenstrauss, Classical Banach 
Spaces II, Berlin: Springer-Verlag, 1977.  

[17]  J. Diestel, Sequences and Series in Banach 
Spaces, New York: Springer-Verlag, 1984.  

[18]  P. Meyer-Nieberg, Banach Lattices, Berlin: 
Springer-Verlag, 1991.  

[19]  F. d. K. N. Albiac, Topics in Banach Space 
Theory, New York: Springer-Verlag, 2006.  

[20]  J. Yeh, Real Analysis: Theory of 
Measure and Integration, 2nd 
edition, Singapore: World 
Scientific Publishing, 2006.  

[21]  H. Dales, Introduction Banach Algebras, 
Operators, and Harmonic Analysis, 
Cambridge: Cambridge University Press, 
2003.  

[22]  S. Darmawijaya, "Calculus on the Family of 
Continuous Functions," in Seminar Nasional 
KNM XVI, Universitas Padjadjaran 
Sumedang, 2012.  

[23]  F. Chorlton, Textbook of fluid dynamics, 
Princeton: D. Van Nostrand Company LTD, 
1967.  

[24]  B. R. Munson, Fundamentals of fluid 
mechanics, John Wiley and Sons, Inc, 2002.  

[25]  R. M. Olson, Dasar-dasar mekanika fluida, 
Jakarta: PT Gramedia Pustaka Utama, 1993.  

[26]  B. K. Shivamoggi, Theoretical fluid 
dynamics, Boston: Martinus Nijhoff 
Publisher, 1985.  

[27]  L. Wiryanto, "A Solitary-like wave 
generated by flow passing a bump," in 
ICMSA 2010, Kuala Lumpur, 2010.  

[28]  T. Akylas, "On the excitation of long 
nonlinear water waves by a moving 
pressure distribution," J. Fluid Mech, pp. 
455-466, 1984.  

[29]  S. Cole, "Transient Waves Produces By Flow 
Past a Bump," Wave Motion, pp. 579-587, 
1985.  

[30]  R. P. C. Steven C. Chapra, Numerical 
Methods for Engineers, Boston: Mc Graw 
Hill.  

[31]  R. L. Burden, Numerical Analysis, Boston: 
Brooks/Cole CENGAGE Learning, 2011.  

[32]  L. Lapidus, Numerical Solution of Partial 
Differential Equations in Science and 
Engineering, Canada: John Wiley & Sons, 
1982.  

[33]  Z. D.-H. R.H.J. Grimshaw, "Generation of 
solitary waves by transcritical flow over a 
step," J. Fluid Mech, pp. 235-254, 2007.  

[34]  B. -F. F. a. T. Mitsui, "A finite Difference 

Method for KdV and KP equations," J. Comp. 
Applied Maths., , pp. 95-116, 1998.  

[35]  P. D. &. R. S. Johnson, Solitons: an 
introduction, Britain: Cambridge university 
press, 1993.  

[36]  F. E. Camfield, Tsunami Engineering, 
Belvoir USA: Coastal Engineering Research 
Center, 1980.  

[37]  J. Park, "Numerical Simulation of Wave 
Propagation using the Shallow Water 
Equation," Harvey Mudd College, 2007. 

[38]  L. H. Holthuijsen, Waves in Oceanic and 
Coastal Waters, Cambridge: Cambridge 
University Press, 2007.  

[39]  K. Satake, Tsunamis: Case Studies and 
Recent Development, Netherland: Springer, 
2005.  

[40]  J. Kampf, Ocean Modelling for Beginners, 
New York: Springer, 2009.  

 
 

 
 
 


	PENDAHULUAN
	KAJIAN TEORI
	1. Graf 𝑮
	2. Derajat Titik
	3. Graf Terhubung
	4. Bilangan Kromatik
	5. Grup Dihedral
	6. Graf Commuting dan Noncommuting

	PEMBAHASAN
	Bilangan Kromatik Pewarnaan Titik dan Sisi Graf Commuting Grup Dihedral
	Teorema 1
	Teorema 2
	Bilangan Kromatik Pewarnaan Titik dan Sisi Graf Noncommuting Grup Dihedral
	Teorema 3
	Teorema 4

	KESIMPULAN
	DAFTAR PUSTAKA