Pelabelan Harmonis Ganjil pada Beberapa Kelas Graf

Abstract

Misalkan  graf dengan himpunan titik  dan himpunan sisi  dengan  dan . Pelabelan harmonis ganjil pada  adalah fungsi injektif  sedemikian hingga fungsi terinduksi  dengan adalah bijektif. Selanjutnya, graf  yang memiliki pelabelan seperti itu, disebut graf harmonis ganjil. Jika , maka pelabelan tersebut dinamakan pelabelan harmonis ganjil kuat. Selanjutnya, graf  memiliki yang pelabelan seperti itu, disebut graf harmonis ganjil kuat. Misalkan  sikel dengan  titik dan  sikel dengan  titik. Maka, graf yang dibentuk dari  dan  dengan menggabungkan sebuah titik  dan sebuah titik  dilambangkan . Graf yang dibentuk dari  dan  dengan menggabungkan sebuah sisi  dan sebuah sisi  dilambangkan . Pada skripsi ini akan dibuktikan bahwa jika  graf harmonis ganjil, maka  adalah graf bipartit. Graf  merupakan graf harmonis ganjil jika dan hanya jika  atau .Ditunjukkan graf  merupakan graf harmonis ganjil, jika  dan bilangan bulat genap. Selanjutnya, jika graf  adalah graf harmonis ganjil kuat dan graf  adalah sebarang graf harmonis ganjil, maka graf  yang diperoleh dengan menghimpitkan sisi  dan  adalah graf harmonis ganjil.