1 PENENTUAN NILAI TOTAL KETIDAKTERATURAN TITIK GRAF SARANG LEBAH Riskawati1*), Nurdin2), Hasmawati3) 1 Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Hasanuddin Jln. Perintis Kemerdekaan, Makassar, Indonesia, Kode Pos 90245
THE TOTAL VERTEH IRREGURARY STRENGTH OF HONEYCOMB GRAPH Riskawati1*), Nurdin2), Hasmawati3) 1 Departement of Mathematic, Faculty of Mathematics and Natural Sciences, Hasanuddin University Perintis Kemerdekaan Street, Makassar, Indonesia, Post Code 90245
ABSTRAK Misalkan sebuah graf
adalah graf sederhana. Untuk sebuah pelabelan
total tidak teratur titik pada
disebut pelabelan-
jika untuk setiap dua titik yang berbeda pada
Bilangan bulat positif terkecil
sedemikian sehingga
berlaku
dimana
mempunyai suatu pelabelan- total tidak
teratur titik disebut nilai total ketidakteraturan titik pada graf , dinotasikan dengan
.
Skripsi ini membahas mengenai penentuan nilai total ketidakteraturan titik pada graf sarang lebah, . Hasil penelitian dalam skripsi ini sebagai berikut :
Kata Kunci : Graf Sarang Lebah, Pelabelan Total Ketidakteraturan Titik, Nilai Total Ketidakteraturan titik.
ABSTRACT For a simple graph
with the vertex set
vertex irregular total -labeling of
and the edge set . A labeling
if for any two different vertices
. The smallest positive integer the total vertex irregularity strength of , denoted by
and
in
is called a we have
such that has a vertex irregular total -labeling is called .
In this paper, we determined the total vertex irregularity strength of Honeycomb graph, result in this paper as follows :
Keywords : Honeycomb Graph, Total Vertex Irregular Labeling, Total Vertex Irregularity Strength.
*
Penulis Koresponden.
E-mail :
[email protected]
where
. The
2 1.
Pendahuluan Teori graf pertama kali diperkenalkan oleh Leonhard Euler pada tahun 1736. Saat itu dia memikirkan kemungkinan untuk menyeberangi semua jembatan di kota Kaliningrad, Rusia, tepat satu kali dan kembali ke tempat semula. Publikasi atas permasalahan ini dan solusi yang ditawarkan saat ini dikenal dengan teori graf. Penelitian mengenai teori graf terus mengalami perkembangan. Salah satu pembahasan yang terus berkembang adalah pelabelan pada graf. Objek kajiannya berupa graf yang secara umum direpresentasikan oleh titik dan sisi serta himpunan bagian bilangan asli yang disebut label. Pertama kali diperkenalkan oleh Sadlack (1964), kemudian Stewart (1966), Kotzig, dan Rosa (1970). 2. Tinjauan Pustaka 2.1 Jenis-Jenis Graf Definisi 2.1.1 Graf siklus untuk dinotasikan adalah suatu graf yang memiliki order dan ukuran dimana setiap titiknya berderajat dua dapat dinotasikan dan sisi dan untuk . Definisi 2.1.2 Graf sarang lebah dibangun dari beberapa graf siklus dinotasikan dengan dimana merupakan lapisan ke-n dari graf sarang lebah. Graf sarang lebah diperoleh dengan menambahkan sebanyak graf siklus pada lintasan terluar .
Gambar 2.1(a) Graf
Gambar 2.1(b) Graf
2.2 Pelabelan Total Ketidakteraturan Titik Definisi 2.2.1 Misalkan adalah graf sederhana. Untuk sebuah pelabelan pelabelan
total tidak teratur titik (total vertex irregularity k-labeling) pada graf
berbeda pada
berlaku
dimana
disebut jika untuk setiap dua titik yang
.
Definisi 2.2.2 Nilai total ketidakteraturan titik (total vertex irregularity strength) dari terkecil
sedemikian sehingga
mempunyai suatu pelabelan-
adalah bilangan bulat positif
total tidak teratur titik, yang dinotasikan dengan
3.
Hasil dan Pembahasan Pada bagian ini akan diuraikan nilai total ketidakteraturan titik pada graf sarang lebah Teorema 3.2.1 Untuk , maka nilai total ketidakteraturan titik dari graf adalah
Bukti: Untuk membuktikan dari
maka digunakan Teorema 2.5.1. Karena
adalah , misal
. Misalkan
diberi label
*
Penulis Koresponden.
E-mail :
[email protected]
dengan maka bobot titik
Maka terdapat dua sisi
maka derajat minimum yang terkait dengan
adalah , yang merupakan bobot terkecil pada
. Bobot
3 titik pada graf
dapat ditulis secara berurutan sebagai berikut
titik terbesar
Bobot
yang merupakan bobot titik yang berderajat 3, sebut titik
Karena pelabelan pada
maka terdapat 3 sisi yang terkait dengan sedemikian sehingga
Maka sedikitnya terdapat satu diantara misalkan
adalah
dengan
, sebut
merupakan bobot dan Misalkan fungsi
, maka dengan nilai lebih besar atau sama dengan
Ini menunjukkan bahwa
Selanjutnya akan ditunjukkan bahwa
Untuk tujuan tersebut, akan dikonstruksi suatu pelabelan
total tidak teratur titik pada
sebagai berikut.
Misalkan
. Untuk konstruksi pelabelan yang dimaksud akan dibagi kedalam 2 kasus yaitu
Kasus I untuk Maka
genap
didefinisikan sebagai berikut
Untuk genap
*
Penulis Koresponden.
E-mail :
[email protected]
4
Untuk ganjil
*
Penulis Koresponden.
E-mail :
[email protected]
5
,
Kasus II untuk Maka
ganjil
didefinisikan sebagai berikut
Untuk genap
*
Penulis Koresponden.
E-mail :
[email protected]
6
, ,
Untuk ganjil
*
Penulis Koresponden.
E-mail :
[email protected]
7
,
Berdasarkan definisi bobot titik, diperoleh
*
Penulis Koresponden.
E-mail :
[email protected]
8 Sehingga dapat disimpulkan bahwa bobot setiap titik pada merupakan suatu pelabelan total tidak teratur titik pada Karena
berbeda . Maka
yang dikonstruksikan tersebut
.
memiliki suatu pelabelan-t total tidak teratur titik, dimana
.
Dengan demikian , diperoleh
Karena
dan
maka ■
4. PENUTUP 4.1 Kesimpulan Dengan menggunakan pelabelan total tidak teratur titik pada graf ketidakteraturan titik graf
maka diperoleh nilai total
adalah
4.2 Saran Pembahasan mengenai pelabelan total tidak teratur titik masih terbuka bagi peneliti lain untuk melanjutkan penelitian ini dan bisa juga melakukan penelitian yang sejenis dengan jenis-jenis graf yang berbeda.
*
Penulis Koresponden.
E-mail :
[email protected]
9 DAFTAR PUSTAKA [1]
Ahmad A., Ahtsham S., Hasni R., Slamin, Total Vertex Irregularity Strength Related Graphs, International Referred Research Journal, (2014) 26(1) : 1-5
[2]
Anholcer M., Palmer C., Irregular Labelings of Circulant Graph. 2011.
[3]
B ca M., Jendrol S., Miller M., Ryan J., On Irregular Total Tabllings, Discrete Mathematics, (2007) 307: 1378 - 1388.
[4]
Chartard G., Lesniak L., Ping Z.,Graph and Digraph (5 th ed.), Boca Raton: CRC Press, 2011.
[5]
Fitria W., Nilai Total Tidak Teratur Sisi dari Graf Sarang Lebah, Institut Teknologi Bandung, 2009.
[6]
Hartsfield N., Ringel G.,Pearls in Graph Theory, Dover, New York, 2003.
[7]
Hungund N. S., Akka D. G., Total Irregularity Strength of Triangular Snake and Double Triangular Snake, International Referred Research Journal, (2011) 3 : 67-69.
[8]
Irawati N., Pelabelan Total Titik Ajaib pada Complit Graph, FMIPA Universitas Diponegoro Semarang, 2010.
[9]
Kotzig A., and Rosa A., Magic Valuations of Finite Graphs, Canadian Mathematical Bulleting, (1970) 13 : 451323.
[10]
Manuel P., Rajan B., Rajaningsih I., Monoca C., On Minimum Metric Dimension of Honeycomb Networks, Journal of Discrete Algorithms, (2008) 6 : 20-27.
[11]
Rajasingh I., Rajan B., Annamma V., On the Total Vertex Irregularity Strength of Cycle Related Graphs and H Graphs, International Journal of Computer Applications, (2012) 52 : 32-37.
[12]
Stewart B.M., Magic Graphs, Canadian Journal of Mathematics,(1966) 18: 1031- 1059
[13]
Stojmenovic I., Honeycomb networks: Topological Properties and Communication Algoritms, IEEE Transactions on Parallel and Dis Systems (1997) 8: 1036-1042
[14]
Wallis W. D., Magic Graphs, Birkh user Boston, New Work, 2011.
[15]
Wijaya K., Slamin, Miller M., On Total Vertex Irregularity Strength of Cocktail Party Graph, Jurnal ILMU DASAR, (2011) 12: 148-151.
*
Penulis Koresponden.
E-mail :
[email protected]
of Ladder
