Perpustakaan Digital ITB

Misalkan G = (V,E) graf sederhana. Sebuah fungsi injektif ro : E ->(1,2,3, 3,..., (E) disebut pelabelan sisi titik-anti ajaib jika setiap dua titik berbeda memiliki bobot yang berbeda. Bobot dari titik u pada V terhadap fungsi ro adalah W (u)= ro (uv). Selanjutnya, ro disebut pelabelan sisi (a,d)-titik-anti ajaib jika ada dua bilangan bulat positif a dan d sehingga W(V ) = (a,a + d,a+2d,...a + ((V)-1)d). Suatu graf bipartit adalah graf yang himpunan titiknya dapat dipartisi ke dalam dua himpunan bebas A dan B sehingga setiap sisinya menghubungkan sebuah titik di A ke sebuah titik di B. Suatu graf bipartit lengkap Kn,m adalah graf bipartit dengan (A)= n, (B) = m dan untuk sebarang dua titik u di A dan v di B, uv adalah sebuah sisi di Kn,m. Matching M < E adalah koleksi dari sisi-sisi sehingga setiap titik v di V terkait pada paling banyak satu sisi di M. Suatu matching dikatakan sempurna jika setiap titik v di V terkait pada tepat satu sisi di M. Pada tesis ini, graf bipartit lengkap Kn,m dikurangi sebuah matching sempurna untuk n lebih besar samadengan 4 dinyatakan oleh Gn. Misalkan t bilangan ganjil dan n bilangan genap yang lebih besar daripada t, dibuktikan bahwa tGn memiliki pelabelan titik-anti ajaib. Selanjutnya, untuk setiap bilangan positif t dan bilangan genap n lebih besar daripada 3, tKn,n memiliki pelabelan sisi titik-anti ajaib . Selain itu, dibuktikan pula graf bipartit lengkap Kn,m dikurangi sebuah matching maksimum mempunyai pelabelan sisi titik-anti ajaib untuk setiap bilangan bulat positif n dan m.