Limits: Journal of Mathematics and Its Applications E-ISSN: 2579-8936 P-ISSN: 1829-605X Vol. 18, No. 2, Nopember 2021, 119-128 DOI: http://dx.doi.org/10.12962/limits.v18i2.6665

## Pewarnaan Total pada Graf Bintang Sierpinski
Siti Khabibah 1 *, Dita Anies Munawwaroh 2 1,2 Departemen Matematika Universitas Diponegoro Semarang Indonesia; Jl. Prof. H. Soedharto, SH * e-mail: khabibah.undip@gmail.com
Diajukan: 2 Maret 2020, Diperbaiki: 1 Agustus 2021, Diterima: 6 September 2021

## Abstrak
Bilangan kromatik total graf G adalah bilangan bulat terkecil k dimana titik-titik dan sisi-sisi graf G dapat diwarnai dengan k warna sedemikian hingga dua titik yang adjecent dan sisi yang insiden dengan titik-titik tersebut diberikan warna yang berbeda.  Dalam paper ini dibahas mengenai pewarnaan total pada Graf Bintang Sierpinski, 𝑆𝑆𝑆𝑆 𝑛𝑛 . Bilangan kromatik untuk pewarnaan total pada Graf 𝑆𝑆𝑆𝑆 𝑛𝑛 adalah 1 untuk 𝑛𝑛 = 1 dan 1 + 3. 2 𝑛𝑛−2 untuk 𝑛𝑛 ≥ 2. Kata Kunci : Graf Bintang Sierpinski, Pewarnaan total, Bilangan Kromatik .

## Abstract
The total Chromatic number of graph G is the least integer k where the vertices and edges of the graph G can be colored with k color so that two vertices are adjecent and the edge which incident with these vertices are given different colors. This paper discusses total coloring on Sierpinski Star Graph, 𝑆𝑆𝑆𝑆 𝑛𝑛 . The chromatic number for total coloring on Graph 𝑆𝑆𝑆𝑆 𝑛𝑛 is 1 for 𝑛𝑛 = 1 and 1 + 3. 2 𝑛𝑛−2 for 𝑛𝑛 ≥ 2. Keywords : Sierpinski Star Graph, Total Coloring, Total chromatic number.

## 1 Pendahuluan
Segitiga Sierpinski merupakan salah satu bentuk fraktal yang menarik untuk dikaji lebih dalam. Salah satu kajian matematika yang berkaitan dengan segitiga sierpinski adalah graf. Pada tahun 1997 Klavzar dan Milutinovic [1] memperkenalkan graf Sierpinski 𝑆𝑆 ( 𝑛𝑛 , 𝑘𝑘 ) yang merupakan generalisasi dari masalah Tower Hanoi. Selain graf Sierpinski , terdapat graf Sierpinski Gasket 𝑆𝑆 𝑛𝑛 yang bentuknya identik dengan segitiga Sierpinski, dengan himpunan titik dan sisi dari graf 𝑆𝑆 𝑛𝑛 adalah titik sudut dan sisi segitiga-segitiga dari segitiga Sierpinski [2]. Selain berupa segitiga ada juga yang berupa bujursangkar yang dikenal dengan graf Square Sierpinski [3].  Survey dan klasifikasi mengenai graf turunan Sierpinski dibahas oleh Andreas dan Sandi [4]. Menggunakan manipulasi pelabelan, Toru Hasunuma [5] mengkonstruksi graf Universaled Sierpinski .
Pembahasan yang menarik dalam graf diantaranya adalah pelabelan. Salah satu bentuk pelabelan pada graf adalah pewarnaan graf,  beberapa artikel yang terkait dengan pewarnaan graf dan graf Sierpinski diantaranya adalah pewarnaan pada graf Sierpinski dan Sierpinski Gasket [6]. Pewarnaan titik, sisi, dan pewarnaan total pada graf Sierpinski dan graf Sierpinski Gasket dibahas

## 120
oleh Jacovac dan Klavzar [7]. Untuk pewarnaan pada graf Square Sierpinski dibahas oleh Xue, Zuo, dan Li [3]. Selanjutnya pada [8] dibahas mengenai pewarnaan pada graf Hanoi dan graf Sierpinski . Pewarnaan total pada graf-graf turunan Sierpinski ditulis pada [9].  Selain pewarnaan titik, sisi dan total, pewarnaan Packing pada graf Sierpinski dibahas oleh Bestjan[10]. Terinspirasi kajian mengenai graf Sierpinski, pada tahun 2017 penulis menyusun graf yang dinamakan graf Bintang Sierpinski berikut pewarnaan titik dan sisinya [11]. Konstruksi grafnya baru dijelaskan secara  geometris  belum mencantumkan definisi secara matematis. Dalam  paper ini  dibahas mengenai graf Bintang Sierpinski menggunakan definisi yang lebih matematis beserta  pewarnaan totalnya.

## 2 Metode Penelitian
Penelitian dilaksanakan dengan terlebih dahulu mengkonstruksi graf Bintang Sierpinski yang dibangun dari segitiga Sierpinski dari iterasi ke-1 sampai dengan iterasi ke- n .  Definisi mengenai graf Bintang Sierpinski secara matematis diberikan berikut keterangan melalui tabel dan gambar. Jumlah titik dan sisi dari graf Bintang Sierpinksi untuk iterasi ke- n diambil dari hasil penelitian sebelumnya.  Selanjutnya  dibahas mengenai pewarnaan  total pada graf Bintang Sierpinski. Pewarnaan total dari graf Bintang Sierpinski disajikan dalam bentuk  fungsi  untuk pewarnaan titik dan sisinya. Bilangan kromatik total hasil pewarnaan pada graf Bintang Sierpinski disajikan dalam bentuk proposisi.

## 3 Hasil dan Pembahasan
Pada bab ini akan diberikan definisi mengenai graf Bintang Sierpinksi beserta penjelasan menggunakan contoh dan gambar. Pewarnaan total pada graf Bintang Sierpinski dilengkapi dengan fungsi dari pewarnaan total beserta hasil pewarnaan untuk titik dan sisinya.
3.1  Graf Bintang Sierpinski
Secara geometris graf Bintang Sierpinski 𝑆𝑆𝑆𝑆 𝑛𝑛 dengan 𝑛𝑛 ≥ 1 didefinisikan sebagai graf yang dibentuk dari segitiga Sierpinski. Himpunan titik dari graf Bintang Sierpinski 𝑆𝑆𝑆𝑆 𝑛𝑛 merupakan himpunan semua segitiga dari segitiga Sierpinski hasil iterasi ke- n, dan titik yang mewakili segitiga pusat disebut titik pusat ( center vertex ), sedangkan himpunan sisinya merupakan himpunan semua sisi yang merupakan persekutuan dari dua segitiga dalam segitiga Sierpinski. Dinamakan Graf Bintang Sierpinski karena bentuk dasarnya merupakan graf bintang dan dibangun dari segitiga Sierpinski. Banyaknya titik dan sisi dari graf 𝑆𝑆𝑆𝑆 𝑛𝑛 dinotasikan dengan | 𝑉𝑉 𝑛𝑛 | dan | 𝐸𝐸 𝑛𝑛 | [11].

## 121
Untuk lebih jelasnya, Tabel 1 berikut menjelaskan bagaimana konstruksi graf Bintang Sierpinski dari  segitiga Sierpinski untuk iterasi 1, 2 dan 3 beserta jumlah titik dan sisi dari masing- masing graf.
Tabel 1. Segitiga Sierpinski dan Graf 𝑆𝑆𝑆𝑆 𝑛𝑛 n Segitiga Sierpinski iterasi ke- n Graf 𝑆𝑆𝑆𝑆 𝑛𝑛 | 𝑉𝑉 𝑛𝑛 | | 𝐸𝐸 𝑛𝑛 | 1 2 3 1 4 13 0 3 15
Secara umum, graf Bintang Sierpinski dijelaskan dalam definisi berikut.
Definisi 1. Graf Bintang Sierpinski, 𝑆𝑆𝑆𝑆 𝑛𝑛 ,  didefinisikan sebagai berikut, untuk 𝑆𝑆𝑆𝑆 1 hanya terdiri atas satu titik, untuk 𝑛𝑛 ≥ 2 , himpunan titik dari 𝑆𝑆𝑆𝑆 𝑛𝑛 terdiri atas ( n- 1) -tupel dari bilangan 0,1,2,3 yaitu 𝑉𝑉 ( 𝑆𝑆𝑆𝑆 𝑛𝑛 ) = {0,1,2,3} 𝑛𝑛−1 . Dua titik 𝑢𝑢 = ( 𝑢𝑢 1 , 𝑢𝑢 2 , … , 𝑢𝑢 𝑛𝑛−1 ) dengan 𝑢𝑢 𝑖𝑖 ∈ {0,1,2,3} dan 𝑣𝑣 = ( 𝑣𝑣 1 , 𝑣𝑣 2 , … , 𝑣𝑣 𝑛𝑛−1 ) dengan 𝑣𝑣 𝑖𝑖 ∈ {1,2,3} dikatakan adjacent jika dan hanya jika terdapat 𝑘𝑘 ∈ {1,2, … , 𝑛𝑛 − 1} sedemikian hingga
i. 𝑢𝑢 𝑖𝑖 = 0 𝑢𝑢𝑛𝑛𝑢𝑢𝑢𝑢𝑘𝑘 𝑖𝑖 = 𝑘𝑘 , 𝑘𝑘 + 1, … , 𝑛𝑛 − 1 ii. 𝑢𝑢 𝑖𝑖 = 𝑣𝑣 𝑖𝑖 𝑢𝑢𝑛𝑛𝑢𝑢𝑢𝑢𝑘𝑘 𝑖𝑖 = 1,2, … , 𝑘𝑘 − 1
iii. 𝑣𝑣 𝑖𝑖 ≠ 𝑣𝑣 𝑘𝑘 𝑢𝑢𝑛𝑛𝑢𝑢𝑢𝑢𝑘𝑘 𝑖𝑖 = 𝑘𝑘 + 1, 𝑘𝑘 + 2, … , 𝑛𝑛 − 1
Selanjutnya titik ( 𝑢𝑢 1 , 𝑢𝑢 2 , … , 𝑢𝑢 𝑛𝑛−1 ) ditulis dengan 〈𝑢𝑢 1 𝑢𝑢 2 … 𝑢𝑢 𝑛𝑛−1 〉 .
Jumlah titik dan sisi pada graf Bintang Sierpinksi ditunjukkan dalam proposisi  berikut:
Proposisi  2 . [11] Graf Bintang Sierpinski 𝑆𝑆𝑆𝑆 𝑛𝑛 mempunyai 1 2 (3 𝑛𝑛 − 1) titik untuk 𝑛𝑛 ≥ 1 dan ∑ 2 𝑖𝑖 . 3 𝑛𝑛−1−𝑖𝑖 𝑛𝑛−2 𝑖𝑖=0 sisi untuk 𝑛𝑛 ≥ 2 .
Setiap graf Bintang Sierpinski, 𝑆𝑆𝑆𝑆 𝑛𝑛 untuk 𝑛𝑛 ≥ 2 memuat tiga subgraf yang identik dengan graf 𝑆𝑆𝑆𝑆 𝑛𝑛−1 . Dalam paper ini subgraf atas, kiri,dan kanan masing-masing dinotasikan dengan 𝑆𝑆𝑆𝑆 𝑛𝑛−1 1 , 𝑆𝑆𝑆𝑆 𝑛𝑛−1 2 , dan 𝑆𝑆𝑆𝑆 𝑛𝑛−1 3 , dan subgraf-subgraf ini pun terdiri atas tiga subgraf dari iterasi
sebelumnya.  Titik pusat utama merupakan titik dengan derajat tertinggi, yaitu titik 〈𝑢𝑢 1 𝑢𝑢 2 … 𝑢𝑢 𝑛𝑛−1 〉 dengan 𝑢𝑢 𝑖𝑖 = 0 untuk semua 𝑖𝑖 . Untuk semua titik 𝑣𝑣 = ( 𝑣𝑣 1 , 𝑣𝑣 2 , … , 𝑣𝑣 𝑛𝑛−1 ) pada 𝑆𝑆𝑆𝑆 𝑛𝑛−1 1 , 𝑆𝑆𝑆𝑆 𝑛𝑛−1 2 , dan 𝑆𝑆𝑆𝑆 𝑛𝑛−1 3 nilai 𝑣𝑣 1 berturut-turut sama dengan 1, 2, dan 3. Untuk 𝑖𝑖 ≠ 1 , 𝑣𝑣 𝑖𝑖 ∈ {0,1,2,3}, untuk titik yang memuat 𝑣𝑣 𝑖𝑖 = 0 merupakan titik pusat dari masing-masing subgraf, sedangkan untuk 𝑣𝑣 𝑖𝑖 ∈ {2,3}, 𝑣𝑣 𝑖𝑖 ∈ {1,3}, dan 𝑣𝑣 𝑖𝑖 ∈ {1,2} berturut-turut  untuk graf 𝑆𝑆𝑆𝑆 𝑛𝑛−1 1 , graf 𝑆𝑆𝑆𝑆 𝑛𝑛−1 2 , dan graf 𝑆𝑆𝑆𝑆 𝑛𝑛−1 3 dihubungkan dengan titik pusat utama.
Contoh 3. Diberikan Graf 𝑆𝑆𝑆𝑆 3 dan 𝑆𝑆𝑆𝑆 4 yang masing-masing mempunyai titik berjumlah 13 dan 40 serta banyaknya sisi masing-masing 15 dan 57.
Gambar 1a . Graf 𝑆𝑆𝑆𝑆 3 Gambar 1b . Graf 𝑆𝑆𝑆𝑆 4 Gambar 1a memperlihatkan bahwa Graf 𝑆𝑆𝑆𝑆 3 mempunyai 13 titik terdiri atas 1 titik pusat utama, 3 titik pusat dari tiga subgraf ( 𝑆𝑆𝑆𝑆 2 1 , 𝑆𝑆𝑆𝑆 2 2 , dan 𝑆𝑆𝑆𝑆 2 3 ), dan 9 titik yang masing-masing adjacent dengan titik pusat pada masing-masing subgraf yang bersesuaian. Titik pusat utama merupakan titik dengan derajat tertinggi, yaitu titik 〈 00 〉 . Titik pusat subgraf 𝑆𝑆𝑆𝑆 2 1 , 𝑆𝑆𝑆𝑆 2 2 , dan 𝑆𝑆𝑆𝑆 2 3 masing-masing adalah titik 〈 10 〉 , 〈 20 〉 , dan 〈 30 〉 . Titik 〈 11 〉 , 〈 12 〉 , dan 〈 13 〉 merupakan titik dari subgraf 𝑆𝑆𝑆𝑆 2 1 yang adjacent dengan 〈 10 〉 . Titik 〈 21 〉 , 〈 22 〉 , dan 〈 23 〉 merupakan titik dari subgraf 𝑆𝑆𝑆𝑆 2 2 yang adjacent dengan 〈 20 〉 . Titik 〈 31 〉 , 〈 32 〉 , dan 〈 33 〉 merupakan titik dari subgraf 𝑆𝑆𝑆𝑆 2 3 yang adjacent dengan 〈 30 〉 . Titik yang adjacent dengan titik pusat utama adalah titik 〈 12 〉 , 〈 13 〉 , 〈 21 〉 , 〈 23 〉 , 〈 31 〉 , dan 〈 32 〉 . Jadi titik-titik pada 𝑆𝑆𝑆𝑆 3 adalah 〈 00 〉 , 〈 10 〉 , 〈 11 〉 , 〈 12 〉 , 〈 13 〉 , 〈 20 〉 , 〈 21 〉 , 〈 22 〉 , 〈 23 〉 , 〈 30 〉 , 〈 31 〉 , 〈 32 〉 , dan 〈 33 〉
Graf 𝑆𝑆𝑆𝑆 4 memuat tiga subgraf yang identik dengan graf 𝑆𝑆𝑆𝑆 3 ditambah dengan satu titik yang disebut titik utama. Titik pusat utamanya adalah titik 〈 000 〉 , sedangkan titik-titik dari subgraf 𝑆𝑆𝑆𝑆 3 1 , 𝑆𝑆𝑆𝑆 3 2 , dan 𝑆𝑆𝑆𝑆 3 3 identik dengan titik-titik pada graf 𝑆𝑆𝑆𝑆 3 . Sebagai contoh, subgraf 𝑆𝑆𝑆𝑆 3 1 mempunyai 13 titik  dan 15 sisi yang identik dengan graf 𝑆𝑆𝑆𝑆 3 . Adapun titik-titik  dari subgraf 𝑆𝑆𝑆𝑆 3 1 adalah
〈 100 〉 , 〈 110 〉 , 〈 111 〉 , 〈 112 〉 , 〈 113 〉 , 〈 120 〉 , 〈 121 〉 , 〈 122 〉 , 〈 123 〉 , 〈 130 〉 , 〈 131 〉 , 〈 132 〉 dan 〈 133 〉 . Untuk titik 〈𝑢𝑢 1 𝑢𝑢 2 𝑢𝑢 3 〉 pada 𝑆𝑆𝑆𝑆 3 2 dan 𝑆𝑆𝑆𝑆 3 3 nilai 𝑢𝑢 1 masing-masing bernilai 2 dan 3, sedangkan 𝑢𝑢 2 dan 𝑢𝑢 3 identik dengan 𝑆𝑆𝑆𝑆 3 1 .
Secara umum setiap graf Bintang Sierpinski, 𝑆𝑆𝑆𝑆 𝑛𝑛 untuk 𝑛𝑛 ≥ 2 memuat tiga subgraf yang identik dengan graf 𝑆𝑆𝑆𝑆 𝑛𝑛−1 yaitu subgraf atas, kiri,dan kanan masing-masing dinotasikan dengan 𝑆𝑆𝑆𝑆 𝑛𝑛−1 1 , 𝑆𝑆𝑆𝑆 𝑛𝑛−1 2 , dan 𝑆𝑆𝑆𝑆 𝑛𝑛−1 3
Pada 𝑆𝑆𝑆𝑆 𝑛𝑛−1 1 , setiap titik 𝑣𝑣 = ( 𝑣𝑣 1 , 𝑣𝑣 2 , … , 𝑣𝑣 𝑛𝑛−1 ) berlaku aturan untuk 𝑖𝑖 = 1 nilai 𝑣𝑣 𝑖𝑖 = 1 dan untuk 𝑖𝑖 ≠ 1 nilai 𝑣𝑣 𝑖𝑖 ∈ {0,1,2,3}, dimana titik yang memuat 𝑣𝑣 𝑖𝑖 = 0 merupakan titik pusat dari subgraf pada 𝑆𝑆𝑆𝑆 𝑛𝑛−1 1 , sedangkan titik-titik 𝑣𝑣 dimana 𝑣𝑣 𝑖𝑖 ∈ {2,3} untuk 𝑖𝑖 ≠ 1 terhubung dengan titik pusat utama.
Pada 𝑆𝑆𝑆𝑆 𝑛𝑛−1 2 berlaku aturan untuk 𝑖𝑖 = 1 nilai 𝑣𝑣 1 = 2 dan untuk 𝑖𝑖 ≠ 1 nilai 𝑣𝑣 𝑖𝑖 ∈ {0,1,2,3}, dimana titik yang memuat 𝑣𝑣 𝑖𝑖 = 0 merupakan titik pusat dari subgraf pada 𝑆𝑆𝑆𝑆 𝑛𝑛−1 2 , sedangkan titik-titik 𝑣𝑣 dimana 𝑣𝑣 𝑖𝑖 ∈ {1,3} untuk 𝑖𝑖 ≠ 1 terhubung dengan titik pusat utama.
Serupa dengan 𝑆𝑆𝑆𝑆 𝑛𝑛−1 1 dan 𝑆𝑆𝑆𝑆 𝑛𝑛−1 2 , nilai 𝑣𝑣 𝑖𝑖 untuk 𝑖𝑖 = 1 pada 𝑆𝑆𝑆𝑆 𝑛𝑛−1 3 selalu bernilai 3, atau 𝑣𝑣 1 = 3 dan untuk 𝑖𝑖 ≠ 1 nilai 𝑣𝑣 𝑖𝑖 ∈ {0,1,2,3}, dimana titik yang memuat 𝑣𝑣 𝑖𝑖 = 0 merupakan titik pusat dari subgraf pada 𝑆𝑆𝑆𝑆 𝑛𝑛−1 2 , sedangkan untuk titik 𝑣𝑣 dimana 𝑣𝑣 𝑖𝑖 ∈ {1,2} untuk 𝑖𝑖 ≠ 1 terhubung dengan titik pusat utama.

## 3.2  Pewarnaan Total pada Graf Bintang Sierpinski
Pewarnaan total dari suatu graf G merupakan fungsi 𝜋𝜋 : 𝑉𝑉 ∪ 𝐸𝐸 → ∁ sedemikian sehingga tidak ada dua elemen adjacent ( yaitu titik dengan titik, sisi dengan sisi, maupun titik dengan sisi yang insiden) yang mempunyai warna yang sama. Bilangan kromatik total dari graf G,yang dinotasikan dengan 𝜆𝜆 𝑇𝑇 ( 𝐺𝐺 ) ,  menunjukkan banyaknya warna minimum yang digunakan pada pewarnaan total graf G. Menurut Vizing  [12],  jika  G adalah graf sederhana dengan  derajat maksimum titik dari G adalah ∆ ( 𝐺𝐺 ) maka 𝜆𝜆 𝑇𝑇 ( 𝐺𝐺 ) ≤ ∆ ( 𝐺𝐺 ) + 2. Ada 2 tipe graf terkait dengan pewarnaan total yaitu graf tipe I dan garf tipe II. Graf  G dikatakan graf tipe I jika jumlah minimal warna pada pewarnaan totalnya adalah ∆ ( 𝐺𝐺 ) + 1 warna atau 𝜆𝜆 𝑇𝑇 ( 𝐺𝐺 ) = ∆ ( 𝐺𝐺 ) + 1 . Selanjutnya graf G dikatakan graf tipe II jika jumlah warna minimal pada pewarnaan totalnya adalah ∆ ( 𝐺𝐺 ) + 2 atau 𝜆𝜆 𝑇𝑇 ( 𝐺𝐺 ) = ∆ ( 𝐺𝐺 ) + 2 .
Graf sikel 𝐶𝐶 𝑛𝑛 merupakan graf dengan ∆ ( 𝐶𝐶 𝑛𝑛 ) = 2 untuk setiap n . Graf sikel 𝐶𝐶 3 termasuk dalam  graf tipe I karena 𝜆𝜆 𝑇𝑇 ( 𝐶𝐶 3 ) = ∆ ( 𝐶𝐶 𝑛𝑛 ) + 1 = 3 . Sedangkan graf sikel 𝐶𝐶 4 merupakan graf tipe II karena 𝜆𝜆 𝑇𝑇 ( 𝐶𝐶 4 ) = ∆ ( 𝐶𝐶 𝑛𝑛 ) + 2 = 4.
Proposisi  3. Bilangan kromatik untuk pewarnaan total graf 𝑆𝑆𝑆𝑆 𝑛𝑛 adalah 1 untuk 𝑛𝑛 = 1 dan 3. 2 𝑛𝑛−2 + 1 untuk 𝑛𝑛 ≥ 2.
Bukti : Untuk 𝑛𝑛 = 1 hanya terdiri atas satu titik sehingga warna yang bisa diaplikasikan hanya ada 1 warna, untuk 𝑛𝑛 = 2 graf 𝑆𝑆𝑆𝑆 𝑛𝑛 identik dengan graf bintang  dengan banyaknya titik  dan sisi masing-masing adalah 4 dan 3. Karena terdapat satu titik berderajat 3 maka jumlah warna minimal yang bisa diaplikasikan adalah 4 yaitu sama dengan derajat maksimum titik ditambah 1, empat warna untuk titik dan 3 warna untuk sisi. Dengan cara yang sama, untuk 𝑛𝑛 ≥ 3 , derajat maksimum titik dari graf 𝑆𝑆𝑆𝑆 𝑛𝑛 adalah 3. 2 𝑛𝑛−2 ,  sehingga graf 𝑆𝑆𝑆𝑆 𝑛𝑛 dapat diwarnai dengan minimal 3. 2 𝑛𝑛−2 + 1 warna. Jadi terbukti bahwa  bilangan kromatik dari 𝑆𝑆𝑆𝑆 𝑛𝑛 adalah 1 untuk 𝑛𝑛 = 1 dan 3. 2 𝑛𝑛−2 + 1 untuk 𝑛𝑛 ≥ 2.
Untuk lebih jelasnya berikut ini diberikan rumus pewarnaan total untuk graf Bintang Sierpinski. Untuk 𝑛𝑛 ≥ 2 diberikan fungsi 𝜋𝜋 : ( 𝑉𝑉 ∪ 𝐸𝐸 )( 𝑆𝑆𝑆𝑆 𝑛𝑛 ) → {0,1, … ,3. 2 𝑛𝑛−2 } ,
Untuk 𝑛𝑛 = 2
Karena graf 𝑆𝑆𝑆𝑆 2 merupakan graf bintang yang terdiri atas 1 titik berderajat 3 dan 3 titik berderajat 1 maka jumlah warna minimalnya adalah 4. Berikut ini rumus pewarnaan total untuk graf 𝑆𝑆𝑆𝑆 2 𝜋𝜋 : ( 𝑉𝑉 ∪ 𝐸𝐸 )( 𝑆𝑆𝑆𝑆 2 ) → {0,1,2,3} ,
𝑉𝑉 ( 𝑆𝑆𝑆𝑆 2 ) = { 〈 0 〉 , 〈 1 〉 , 〈 2 〉 , 〈 3 〉 } dan 𝐸𝐸 ( 𝑆𝑆𝑆𝑆 2 ) = { 〈 0 〉〈 1 〉 , 〈 0 〉〈 2 〉 , 〈 0 〉〈 3 〉 }
Pewarnaan titik : 𝜋𝜋 ( 〈 0 〉 ) = 0 𝜋𝜋 ( 〈 1 〉 ) = 1 𝜋𝜋 ( 〈 2 〉 ) = 2
𝜋𝜋 ( 〈 3 〉 ) = 3 Pewarnaan sisi:
𝜋𝜋 ( 〈 0 〉〈 1 〉 ) = 2 𝜋𝜋 ( 〈 0 〉〈 2 〉 ) = 3 𝜋𝜋 ( 〈 0 〉〈 3 〉 ) = 1
Gambar 2a . Graf 𝑆𝑆𝑆𝑆 2
Gambar 2b
. Pewarnaan pada graf 𝑆𝑆𝑆𝑆 2
Untuk 𝑛𝑛 = 3,
Graf 𝑆𝑆𝑆𝑆 3 terdiri atas tiga subgraf yang identik dengan 𝑆𝑆𝑆𝑆 2 yaitu 𝑆𝑆𝑆𝑆 2 1 , 𝑆𝑆𝑆𝑆 2 2 , dan 𝑆𝑆𝑆𝑆 2 3 . Pewarnaan titik dan sisi pada masing-masing subgraf  sama dengan pewarnaan pada graf 𝑆𝑆𝑆𝑆 2 . Untuk titik

## 125
pusat pada 𝑆𝑆𝑆𝑆 3 diberi warna 0, sedangkan pewarnaan untuk sisi-sisi yang insiden dengan titik pusat diberi warna 1 sampai dengan 3. 2 𝑛𝑛−2 searah jarum jam dimulai dari sisi yang insident dengan titik dari subgraf 𝑆𝑆𝑆𝑆 2 1 . Berikut adalah hasil pewarnaan pada graf 𝑆𝑆𝑆𝑆 3 .
𝜋𝜋 : ( 𝑉𝑉 ∪ 𝐸𝐸 )( 𝑆𝑆𝑆𝑆 3 ) → {0,1,2,3,4,5,6} ,
𝑉𝑉
( 𝑆𝑆𝑆𝑆 3 ) = { 〈 00 〉
, 〈 10 〉 ,
〈 11 〉 , 〈 12 〉 , 〈 13 〉 , 〈 20 〉 , 〈 21 〉 , 〈 22 〉 , 〈 23 〉 , 〈 30 〉 , 〈 31 〉 , 〈 32 〉 , 〈 33 〉 } dan 𝐸𝐸 ( 𝑆𝑆𝑆𝑆 2 ) = { 〈 10 〉〈 11 〉 , 〈 10 〉〈 12 〉 , 〈 10 〉〈 13 〉 , 〈 20 〉〈 21 〉 , 〈 20 〉〈 22 〉 , 〈 20 〉〈 23 〉 , 〈 30 〉〈 31 〉 ,
〈 30 〉〈 32 〉 , 〈 30 〉〈 33 〉 , 〈 00 〉〈 12 〉 , 〈 00 〉〈 13 〉 , 〈 00 〉〈 21 〉 , 〈 00 〉〈 23 〉 , 〈 00 〉〈 31 〉 , 〈 00 〉〈 32 〉 }
Pewarnaan titik :
𝜋𝜋 ( 〈 00 〉 ) = 0 𝜋𝜋 ( 〈 10 〉 ) = 0 𝜋𝜋 ( 〈 20 〉 ) = 0 𝜋𝜋 ( 〈 30 〉 ) = 0 𝜋𝜋 ( 〈 11 〉 ) = 1 𝜋𝜋 ( 〈 21 〉 ) = 1 𝜋𝜋 ( 〈 31 〉 ) = 1 𝜋𝜋 ( 〈 12 〉 ) = 2 𝜋𝜋 ( 〈 22 〉 ) = 2 𝜋𝜋 ( 〈 32 〉 ) = 2 𝜋𝜋 ( 〈 13 〉 ) = 3 𝜋𝜋 ( 〈 23 〉 ) = 3 𝜋𝜋 ( 〈 33 〉 ) = 3
Pewarnaan sisi:
𝜋𝜋 ( 〈 10 〉〈 11 〉 ) = 2
𝜋𝜋 ( 〈 10 〉〈 12 〉 ) = 3
𝜋𝜋 ( 〈 10 〉〈 13 〉 ) = 1 𝜋𝜋 ( 〈 20 〉〈 21 〉 ) = 2 𝜋𝜋 ( 〈 20 〉〈 22 〉 ) = 3
𝜋𝜋 ( 〈 20 〉〈 23 〉 ) = 1
𝜋𝜋 ( 〈 30 〉〈 31 〉 ) = 2
𝜋𝜋 ( 〈 30 〉〈 32 〉 ) = 3
𝜋𝜋 ( 〈 30 〉〈 33 〉 ) = 1 𝜋𝜋 ( 〈 00 〉〈 12 〉 ) = 1 𝜋𝜋 ( 〈 00 〉〈 13 〉 ) = 2 𝜋𝜋 ( 〈 00 〉〈 31 〉 ) = 3 𝜋𝜋 ( 〈 00 〉〈 32 〉 ) = 4
𝜋𝜋 ( 〈 00 〉〈 21 〉 ) = 5 𝜋𝜋 ( 〈 00 〉〈 23 〉 ) = 6 Gambar 3a . Graf 𝑆𝑆𝑆𝑆 3
Gambar 3b . Pewarnaan pada graf 𝑆𝑆𝑆𝑆 3

## 126
Selanjutnya secara umum rumus pewarnaan total untuk 𝑆𝑆𝑆𝑆 𝑛𝑛 untuk 𝑛𝑛 ≥ 2 adalah sebagai berikut: 𝜋𝜋 : ( 𝑉𝑉 ∪ 𝐸𝐸 )( 𝑆𝑆𝑆𝑆 𝑛𝑛 ) → {0,1, … ,3. 2 𝑛𝑛−2 }
Pewarnaan titik : 𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−1 〉 ) = 𝑢𝑢 𝑛𝑛−1 , dengan 𝑢𝑢 𝑛𝑛−1 ∈ {0,1,2,3}
Pewarnaan sisi :
untuk 𝑢𝑢 𝑖𝑖 ≠ 0 𝑢𝑢𝑛𝑛𝑢𝑢𝑢𝑢𝑘𝑘 𝑖𝑖 = 1,2, … , 𝑛𝑛 − 2 , pewarnaan sisi dari graf 𝑆𝑆𝑆𝑆 𝑛𝑛 adalah sebagai berikut. 𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−2 0 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−2 1 〉 ) = 2 , 𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−2 0 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−2 2 〉 ) = 3, 𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−2 0 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−2 3 〉 ) = 1,
untuk 𝑢𝑢 𝑖𝑖 ≠ 0 𝑢𝑢𝑛𝑛𝑢𝑢𝑢𝑢𝑘𝑘 𝑖𝑖 = 1,2, … , 𝑛𝑛 − 3 , pewarnaan sisi dari graf 𝑆𝑆𝑆𝑆 𝑛𝑛 adalah sebagai berikut.
𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−3 00 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−3 12 〉 ) = 1 ,
𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−3 00 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−3 13 〉 ) = 2,
𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−3 00 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−3 31 〉 ) = 3,
𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−3 00 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−3 32 〉 ) = 4 , 𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−3 00 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−3 21 〉 ) = 5,
𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−3 00 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−3 23 〉 ) = 6,
Selanjutnya untuk suatu bilangan bulat positif 𝑘𝑘 ∈ {1,2, … , 𝑛𝑛 − 1} dan 𝑛𝑛 ≥ 3 , berlaku pewarnaan sisi sebagai berikut.
𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 0 … 0 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 13 … 32 〉 ) = 1 𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 0 … 0 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 13 … 33 〉 ) = 2
jika 𝑢𝑢 𝑘𝑘 = 3 dan 𝑢𝑢 𝑖𝑖 ∈ {1,2} untuk 𝑖𝑖 = 𝑘𝑘 + 1, 𝑘𝑘 + 2, . . . 𝑛𝑛 − 1 , maka
𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 0 … 0 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 31 … 11 〉 ) = 3 𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 0 … 0 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 31 … 12 〉 ) = 4
𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 0 … 0 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 32 … 22 〉 ) = 2 + 2 𝑘𝑘−1
jika 𝑢𝑢 𝑘𝑘 = 2 dan 𝑢𝑢 𝑖𝑖 ∈ {1,3} untuk 𝑖𝑖 = 𝑘𝑘 + 1, 𝑘𝑘 + 2, . . . 𝑛𝑛 − 1 , maka 𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 0 … 0 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 23 … 33 〉 ) = 2 + 2 𝑘𝑘−1 + 1
𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 0 … 0 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 21 … 11 〉 ) = 2 + 2.2 𝑘𝑘−1
jika 𝑢𝑢 𝑘𝑘 = 1 dan 𝑢𝑢 𝑖𝑖 ∈ {2,3} untuk 𝑖𝑖 = 𝑘𝑘 + 1, 𝑘𝑘 + 2, . . . 𝑛𝑛 − 1 , maka 𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 0 … 0 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 12 … 22 〉 ) = 2 + 2. 2 𝑘𝑘−1 + 1
𝜋𝜋 ( 〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 0 … 0 〉〈𝑢𝑢 1 … 𝑢𝑢 𝑛𝑛−𝑘𝑘−1 13 … 23 〉 ) = 3. 2 𝑘𝑘−1
untuk subgraf 𝑆𝑆𝑆𝑆 𝑛𝑛 sama dengan pewarnaan graf 𝑆𝑆𝑆𝑆 𝑛𝑛−1 , dan untuk sisi yang insiden dengan titik pusat diberi warna 1,2,..., 3. 2 𝑛𝑛−2 berurutan searah jarum jam dimulai dari dua sisi paling kanan dari subgraf 𝑆𝑆𝑆𝑆 𝑛𝑛−1 1 yang insiden dengan titik pusat utama.

## 4  Simpulan
Berdasarkan pembahasan mengenai konstruksi dan pewarnaan total pada graf Bintang Sierpinski diperoleh kesimpulan bahwa graf Bintang Sierpinski merupakan graf yang serupa dengan dirinya atau self similar . Untuk bilangan kromatik pewarnaan total pada graf Bintang Sierpinski sama dengan derajat tertinggi titiknya ditambah satu. Titik yang mempunyai derajat tertinggi adalah titik pusat utama.

## 5  Daftar Pustaka
[1] S. Klavžar and U. Milutinović, “Graphs S(n, k) and a variant of the tower of Hanoi problem,” Czechoslov. Math. J. , vol. 47, no. 1, pp. 95–104, 1997, doi: 10.1023/A:1022444205860.
[2] A. M. Teguia and A. Godbole, “Sierpi ´ nski Gasket Graphs and Some of Th eir Properties,” Australas. J. Comb. , vol. 35, pp. 181–192, 2006.
[3] B. Xue, L. Zuo, and G. Li, “Coloring the Square of Sierpiński Graphs,” Graphs Comb. , vol. 31, no. 5, pp. 1795–1805, 2015, doi: 10.1007/s00373-014-1444-y.
[4] A. M. Hinz, S. Klavžar, and S. S. Zemljič, “A survey and classification of Sierpiński -type graphs,” Discret. Appl. Math. , vol. 217, pp. 565–600, 2017,
doi: 10.1016/j.dam.2016.09.024.
[5] T. Hasunuma, “Constructions of universalized Sierpiński graphs based on labeling manipulations,” Electron. Notes Discret. Math. , vol. 60, pp. 47–54, 2017.
[6] S. Klavzar, “COLORING SIERPIN´ SKI GRAPHS AND SIERPIN´ SKI GASKET GRAPHS,” Taiwan. J. Math. , vol. 12, no. 2, pp. 513–522, 2008.
[7] M. Jakovac and S. Klavžar, “Vertex -, edge-, and total-colorin gs of Sierpiński -like graphs,” Discrete Math. , vol. 309, no. 6, pp. 1548–1556, 2009,
doi: 10.1016/j.disc.2008.02.026.
[8] A. M. Hinz and D. Parisse, “Coloring Hanoi and Sierpiski graphs,” Discrete Math. , vol.
312, no. 9, pp. 1521–1535, 2012, doi: 10.1016/j.disc.2011.08.019.
[9] J. Geetha and K. Somasundaram, “Total coloring of generalized sierpiński graphs,” Australas. J. Comb. , vol. 63, no. 1, pp. 58–69, 2015.
[10] B. Brešar and J. Ferme, “Packing coloring of Sierpiński -type graphs,” Aequationes Math. , vol. 92, no. 6, pp. 1091–1118, 2018, doi: 10.1007/s00010-018-0561-8.
[11] S. Khabibah, “PEWARNAAN PADA GRAF BINTANG SIERPINSKI,” J. Ilm. Mat. dan Pendidik. Mat. , vol. 9, no. 1, pp. 37–44, 2017.
[12] V. Vizing, “On an estimate of the chromatic class o f a p-graph,” Disk. Anal. , vol. 3, pp. 25–30, 1964.