Menentukan bilangan cover titik dan cover sisi pada graf komplit K_n, graf bipartisi komplit K_n,n dan graf bipartisi komplit K_m,n dengan m,n∈N

Sebuah titik dan sisi dikatakan saling cover pada graf G jika titik dan sisi tersebut incident pada G. Titik cover di G merupakan himpunan dari titik-titik yang mengcover semua sisi di G dan sisi cover pada graf G (tanpa titik terisolasi) merupakan himpunan sisi-sisi yang mengcover semua titik di G. Kardinalitas minimum titik cover pada graf G disebut bilangan cover titik (vertex covering number) dan dilambangkan dengan α(G). Sedangkan kardinalitas minimum sisi cover pada graf G disebut bilangan cover sisi (edge covering number) dan dilambangkan dengan α1(G). Skripsi ini membahas penentuan bilangan cover titik dan cover sisi pada graf komplit Kn, graf bipartisi komplit Kn,n dan graf bipartisi komplit K_m,n.

Penelitian ini dilakukan dengan tujuan untuk mengetahui cara menentukan bilangan cover titik dan cover sisi pada graf komplit K_n, graf bipartisi komplit Kn,n dan graf bipartisi komplit K_m,n.

Berdasarkan hasil pembahasan, langkah-langkah yang dilakukan dalam membahas penelitian ini adalah sebagai berikut: a) Menggambar beberapa contoh graf komplit dan graf bipartisi komplit, b) Mencari himpunan cover titik dan himpunan cover sisi pada beberapa contoh graf komplit dan graf bipartisi komplit, c) Menentukan bilangan cover titik dan cover sisi dengan menghitung kardinalitas minimum dari himpunan cover titik dan himpunan cover sisi, dan d) Mencari pola dari bilangan cover titik dan cover sisi pada graf komplit dan graf bipartisi komplit. Pola tersebut kemudian dirumuskan sebagai konjektur dan dibuktikan kebenarannya. Berdasarkan langkah-langkah tersebut, diperoleh bahwa:
1. Jika K_n adalah graf komplit dengan n∈N, maka rumus bilangan cover titik dan cover sisi masing-masing adalah
...
2. Jika K_n,n adalah graf bipartisi komplit dengan n∈N, maka rumus bilangan cover titik dan cover sisi masing-masing adalah
...
3. Jika K_m,n adalah graf bipartisi komplit dengan m, n dan m∈n, maka rumus bilangan cover titik dan cover sisi masing-masing adalah
...