\documentclass{template-jurnal} %Bagian ini diedit oleh editor Jurnal Matematika UNAND \hyphenation{di-tulis-kan di-terang-kan} %Perhatikan aturan penulisan dan ukuran huruf yang digunakan \begin{document} \markboth{Abdul Majid dkk.} %Jika lebih dari dua penulis, tuliskan sebagai Nama Penulis Pertama dkk. {Bilangan Ramsey Multipartit Himpunan (R-M-H) $M_j (C_n,C_s)$ untuk {\em Cycle}} %%%%%%%%%%%%%%%%%%%%% Publisher's Area please ignore %%%%%%%%%%%%%%% % \catchline{}{}{}{}{} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{BILANGAN RAMSEY MULTIPARTIT HIMPUNAN (R-M-H) $M_j (C_n,C_s)$ UNTUK {\em CYCLE}} \author{ABDUL MAJID\footnote{coresponding author}, SYAFRIZAL SY, ADMI NAZRA\\} \address{Program Studi S1 Matematika,\\ Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Andalas,\\ Kampus UNAND Limau Manis Padang, Indonesia.\\ email : \email{abdulmajidetos18@gmail.com}} \maketitle \setcounter{page}{1} %bagian ini diedit oleh editor Jurnal Matematika UNAND \begin{abstract} \begin{center} %Diterima ..... \quad Direvisi ..... \quad Dipublikasikan ..... %tanggal-tanggal tersebut \textbf{dikosongkan} saja \end{center} \bigskip \textbf{Abstrak}. %Dalam bahasa Indonesia Diberikan dua graf $G$ dan $H$ sembarang. Bilangan Ramsey multipartit himpunan (R-M-H) $M_j(G,H)$ dengan bilangan asli $j \geq 2$, adalah bilangan bulat positif terkecil $t$ sedemikian sehingga jika semua sisi dari graf multipartit seimbang lengkap $K_{t \times j}$ diberi sebarang $2-$pewarnaan merah-biru, maka graf $K_{t \times j}$ senantiasa memuat $G$ berwarna merah sebagai subgraf atau $H$ berwarna biru sebagai subgraf. Graf $C_n$ adalah suatu graf {\em cycle} dengan $n\geq3$ titik. Pada artikel ini, Penulis akan menentukan bilangan R-M-H $M_j(C_n, C_s)$ untuk sebarang bilangan asli $n\geq3$ ganjil dan $s\geq 3$. Hasil dari penelitian ini adalah ditemukannya bilangan R-M-H $M_j(C_n, C_s)$ untuk \textit{cycle}. \end{abstract} \keywords{Bilangan R-M-H; Graf A.Majid; Graf \textit{cycle}; \textit{Matching}} \section{Pendahuluan} Pada tahun 2000, Goddard, Michael, dan Ortrud mendefinisikan bilangan Ramsey bipartit\cite{4}. Kemudian, bilangan Ramsey bipartit berkembang menjadi bila-ngan Ramsey multipartit. Bilangan Ramsey Multipartit diperluas menjadi bilangan Ramsey Multipartit Himpunan (R-M-H) dan bilangan Ramsey Multipartit Ukuran (R-M-U) yang dijelaskan Burger dan Vuuren dalam \cite{2} dan \cite{3} pada tahun 2004. Konsep dari bilangan R-M-H yaitu minimum $t$ dari graf multipartit seimbang lengkap $K_{t \times j}$ yang terdiri dari $t$ himpunan partit dan $j$ banyaknya titik pada setiap himpunan partit. ~\\Beberapa bilangan R-M-H dalam \cite{7}, antara lain: \begin{enumerate} \item[1.] Untuk $3\leq s\leq4$, $M_2(P_2, P_s)=2$. \item[2.] Untuk $5\leq s\leq6$, $M_2(P_2, P_s)=3$. \item[3.] Untuk $3\leq s\leq6$, $M_2(P_3, P_s)=3$. \item[4.] Untuk $3\leq t\leq6$, $M_3(P_3, k_{1,t})=3$. \end{enumerate} \noindent Pada artikel ini, akan ditentukan bilangan R-M-H yang memuat graf \textit{cycle} ganjil dan graf \textit{cycle}. Dengan kata lain, akan ditentukan bilangan R-M-H $M_j(C_n, C_s)$ untuk \textit{cycle}. \section{Landasan Teori} Pada \cite{1}, suatu {\bf graf} $G$ adalah pasangan himpunan terurut $G=(V (G),E(G))$, dimana $V (G)$ adalah suatu himpunan tak kosong yang elemen-elemennya disebut \textbf{titik} dan $E(G)$ adalah suatu himpunan yang elemen-elemennya disebut \textbf{sisi}. Selanjutnya suatu \textbf{\textit{matching}} $M$ pada graf $G$ adalah himpunan sisi dari graf $G$ yang saling lepas sehingga $M\subseteq E(G)$. Kardinalitas $M$ disebut sebagai banyak sisi dari \textit{matching}. Jika setiap titik dari graf $G$ terkait dengan sisi dari $M$, maka $M$ tersebut disebut \textbf{\textit{matching} sempurna}. Suatu \textit{matching} $M$ dikatakan \textbf{\textit{matching} maksimal} jika tidak dapat diperluas menjadi \textit{matching} yang lebih dari $M$. Jika $M$ adalah suatu \textit{matching} sempurna, maka $M$ adalah \textit{matching} maksimal, namun sebaliknya tidak berlaku. ~\\\textbf{Graf \textit{cycle}} adalah graf terhubung yang setiap titik berderajat dua dan disebut juga graf terhubung $2-$\textit{reguler}. Graf cycle dinotasikan dengan $C_n$. Panjang dari $C_n$ adalah banyak sisi yang terdapat di $C_n$ yaitu $n$. Jika terdapat suatu graf $G$ sembarang, maka graf \textit{cycle} maksimalnya adalah graf $C_n$ dengan $n$ terbesar yang dapat dibentuk di $G$. Selanjutnya \textbf{graf multipartit seimbang lengkap} adalah graf multipartit lengkap dengan kardinalitas titik pada setiap himpunan partitnya sama. Graf multipartit seimbang lengkap dengan banyak himpunan partitnya $t$ dan kardinalitas titik pada setiap himpunan partitnya $j$, dinotasikan $K_{t \times j}$ \cite{5}. ~\\Pada tahun 2004 Burger dan Van Vuuren mendefinisikan bilangan Ramsey multipartit himpunan sebagai berikut: \begin{definition} \cite{2} \label{th1} Misalkan $j,l,n,s,$ dan $t$ merupakan bilangan bulat positif dengan $n,s \geq 2$. Bilangan Ramsey multipartit-himpunan $M_j (K_{n \times l},K_{s \times t})$ merupakan bila-ngan bulat positif terkecil $\zeta$ sedemikian sehingga, jika semua sisi dari graf multipartit seimbang lengkap $K_{\zeta \times j}$ diberi dua pewarnaan merah-biru, maka graf multipartit seimbang lengkap $K_{\zeta \times j}$ akan memuat $K_{n \times l}$ merah atau $K_{s \times t}$ biru sebagai subgraf. \end{definition} ~\\Selanjutnya, Definisi 2.1 akan diperumum untuk graf yang tak harus lengkap, yaitu untuk sebarang graf $G$ dan $H$ yang dimuat dalam bilangan R-M-H. Berikut definisi bilangan R-M-H dengan $2-$pewarnaan: \begin{definition} \emph{\cite{6}} $M_j(G,H)$ dengan $2-$pewarnaan. Diberikan dua graf $G$ dan $H$, dan bilangan asli $j \geq 2$. Bilangan Ramsey multipartit $M_j(G,H)$ adalah bilangan bulat positif terkecil $t$ sedemikian sehingga jika semua sisi dari graf multipartit seimbang lengkap $K_{t \times j}$ diberi sebarang $2-$pewarnaan merah-biru, maka graf $K_{t \times j}$ akan memuat graf $G$ berwarna merah atau graf $H$ berwarna biru, sebaliknya. \end{definition} \begin{theorem} $\cite{1}$ \label{def1} Suatu graf $G$ dikatakan graf bipartit jika dan hanya jika graf $G$ tersebut tidak memuat \textit{cycle} ganjil. \end{theorem} \section{BILANGAN R-M-H $M_j (C_n,C_s)$ UNTUK \textit{Cycle}} Pada bagian ini, akan didefinisikan suatu graf yang membantu dalam menentukan bilangan R-M-H $M_j(C_n,C_s)$ untuk \textit{cycle}. Perhatikan Definisi 3.1 berikut ini. \begin{definition} \label{th1} Misalkan $G$ sebarang graf multipartit seimbang lengkap $K_{(t \times j)}$. Mi-salkan $V=V_1\cup V_2\cup ...\cup V_t$ dengan $V_1,V_2,...,V_t$ adalah himpunan partit dari graf $G$. Jika graf $M \subseteq G$ dengan $M = M_1[A_1] \cup \overline{A_1} \oplus M_2[A_2] \cup \overline{A_2} \oplus ... \oplus M_{t-1}[A_{t-1}] \cup \overline{A_{t-1}}$ untuk $A_i = V_1\cup V_{i+1} ; i = 1,2, ... ,t-1$ maka graf $M$ disebut \textbf{graf A.Majid} $M_{t \times j}$. \end{definition} ~\\Berikut disajikan ilustrasi untuk graf A.Majid $M_{(3 \times 3)}$ dengan $M = M_1[A_1] \cup \overline{A_1} \oplus M_2[A_2] \cup \overline{A_2}$ untuk $A_i = V_1\cup V_{i+1} ; i=1,2$. Perhatikan Gambar 1 berikut ini. \begin{figure}[h] \begin{center} \includegraphics[scale=0.7]{ab12} \caption{Faktorisasi graf A.Majid $M_{(3 \times 3)}$} \end{center} \end{figure} ~\\Berdasarkan Definisi 3.3, graf A.Majid memuat beberapa graf bipartit lengkap. Oleh karena itu, graf A.Majid tidak memuat \textit{cycle} ganjil. Hal ini disebabkan karena pada Teorema 2.3, graf bipartit tidak memuat \textit{cycle} ganjil. Selanjutnya, perhatikan beberapa teorema dalam menentukan bilangan R-M-H $M_j(C_n,C_s)$ untuk \textit{cycle}. \begin{theorem} \label{prop1} $M_j(C_n,C_s) = 3$ untuk $j \geq2$, $n$ ganjil, dan $s$ genap dengan $s \leq2j$. \end{theorem} \begin{proof} ~\\Pertama-tama akan ditunjukkan $M_j(C_n,C_s) \geq3$ untuk $j \geq2$, $n$ ganjil, dan $s$ genap dengan $s \leq2j$. Misalkan graf $F=K_{(3-1) \times j}$. Beri $2-$pewarnaan merah-biru pada semua sisi graf $F$. Berdasarkan Teorema 2.3, $F$ tidak memuat \textit{cycle} ganjil karena $F$ graf bipartit. Oleh karena itu, diperoleh $M_j(C_n,C_s) > 2$ untuk $j \geq2$, $n$ ganjil, dan $s \geq 3$. Akibatnya, $M_j(C_n,C_s) \geq3$ untuk $j \geq2$, $n$ ganjil, dan $s$ genap dengan $s \leq2j$. ~\\Selanjutnya akan ditunjukkan $M_j(C_n,C_s) \leq3$ untuk $j \geq2$, $n$ ganjil, dan $s$ genap dengan $s \leq2j$. Misalkan diberi $2-$pewarnaan merah-biru pada semua sisi graf $G = K_{3 \times j}$ sedemikian sehingga $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Akan ditunjukkan bahwa $G_2$ memuat $C_s$ biru untuk $s$ genap dengan $s \leq 2j$. Agar $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Perhatikan dua kasus berikut ini: ~\\\noindent\textbf{Kasus 1.} $G_1$ adalah graf A.Majid $M_{3 \times j}$. ~\\Graf A.Majid tidak memuat \textit{cycle} ganjil sehingga $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Berdasarkan Teorema 2.3, $G_2$ tidak memuat \textit{cycle} ganjil karena $G_2$ graf bipartit. Kemudian $G_2$ memiliki titik sebanyak $2j$. Oleh karena itu, $G_2$ memuat \textit{cycle} genap dengan $C_{2j}$ adalah \textit{cycle} maksimalnya. Akibatnya, $M_j(C_n,C_s) \leq3$ untuk $j \geq2$, $n$ ganjil, dan $s$ genap dengan $s \leq2j$. ~\\\noindent \textbf{Kasus 2.} $G_1$ adalah \textit{matching}. ~\\\textit{Matching} $G_1$ pada graf $G$ adalah himpunan sisi dari graf $G$ yang saling lepas sehingga $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Selanjutnya $G$ memiliki titik sebanyak $3j$. Berdasarkan banyak titik di $G_1$, \textit{matching} $G_1$ dibagi menjadi 2 jenis: \begin{enumerate} \item[\textbf{(a)}] Jika banyak titik di $G_1$ genap maka $G_1$ \textit{matching} sempurna. Oleh karena itu, setiap titik di $G_1$ memiliki derajat 1 sehingga setiap titik di $G_2$ memiliki derajat $2j-1$. Hal ini disebabkan setiap titik di $G$ memiliki derajat $2j$. Akibatnya, $G_2$ memuat \textit{cycle} dengan $C_{3j}$ adalah \textit{cycle} maksimalnya.\\ \item[\textbf{(b)}] Jika banyak titik di $G_1$ ganjil maka $G_1$ \textit{matching} maksimal. Oleh karena itu, $\bigtriangleup(G_1)=1$ sehingga $ \delta(G_2)=2j-1$. Hal ini disebabkan setiap titik di $G$ memiliki derajat $2j$. Akibatnya, $G_2$ memuat \textit{cycle} dengan $C_{3j}$ adalah \textit{cycle} maksimalnya.\\ \noindent Dari \textbf{(a)} dan \textbf{(b)} diperoleh bahwa $G_2$ memuat \textit{cycle} dengan $C_{3j}$ adalah \textit{cycle} maksimalnya. \end{enumerate} Dari \textbf{Kasus 1} dan \textbf{Kasus 2} diperoleh bahwa $G_2$ memuat \textit{cycle} $C_s$ untuk $s \leq3j$. Oleh karena itu, $G_2$ memuat \textit{cycle} genap dengan $s \leq2j$. Akibatnya, $M_j(C_n,C_s) \leq3$ untuk $j \geq2$, $n$ ganjil, dan $s$ genap dengan $s \leq2j$. ~\\\noindent Berdasarkan hal di atas, diperoleh bahwa $M_j(C_n,C_s) \geq3$ untuk $j \geq2$, $n$ ganjil, dan $s$ genap dengan $s \leq2j$ serta $M_j(C_n,C_s) \leq3$ untuk $j \geq2$, $n$ ganjil, dan $s$ genap dengan $s \leq2j$. Oleh karena itu, $M_j(C_n,C_s) = 3$ untuk $j \geq2$, $n$ ganjil, dan $s$ genap dengan $s \leq2j$. \end{proof} \begin{theorem} \label{prop1} $M_j(C_n,C_s) = 4$ untuk $j \geq2$, $n$ ganjil, dan $((s$ ganjil dengan $s < 2j)$ $ \text{atau} $ $(2j < s \leq 3j))$. \end{theorem} \begin{proof} ~\\Pertama-tama akan ditunjukkan $M_j(C_n,C_s) \geq 4$ untuk $j \geq2$, $n$ ganjil, dan $((s$ ganjil dengan $s < 2j)$ $ \text{atau} $ $(2j < s \leq 3j))$. Misalkan graf $F=K{(4-1) \times j}$. Beri $2-$ pewarnaan merah-biru pada semua sisi graf $F$ sebagai berikut: warna merah untuk semua sisi $F_1$ dengan $F_1$ graf Majid $M_{3 \times j}$ dan warna biru pada semua sisi $F_2$ dengan $F_2 = \bar{F_1}$. Berdasarkan Definisi 3.1, $F_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Kemudian berdasarkan Teorema 2.3, $F_2$ tidak memuat \textit{cycle} ganjil biru dengan $C_{2j}$ sebagai \textit{cycle} maksimalnya. Selanjutnya $F_2$ tidak memuat $C_s$ dengan $s > 2j$ karena $C_{2j}$ adalah \textit{cycle} maksimal $F_2$. Akibatnya, $M_j(C_n,C_s) \geq 4$ untuk $j \geq2$, $n$ ganjil, dan $((s$ ganjil dengan $s < 2j)$ $ \text{atau} $ $(2j < s \leq 3j))$. ~\\Selanjutnya akan ditunjukkan $M_j(C_n,C_s) \leq 4$ untuk $j \geq2$, $n$ ganjil, dan $((s$ ganjil dengan $s < 2j)$ $ \text{atau} $ $(2j < s \leq 3j))$. Misalkan diberi $2-$pewarnaan merah-biru pada semua sisi graf $G = K_{4 \times j}$ sedemikian sehingga $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Akan ditunjukkan bahwa $G_2$ memuat $C_s$ biru untuk $((s$ ganjil dengan $s < 2j)$ $ \text{atau} $ $(2j < s \leq 3j))$. Agar $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil, perhatikan dua kasus berikut ini: ~\\\noindent\textbf{Kasus 1.} $G_1$ adalah graf A.Majid $M_{4 \times j}$. ~\\Graf A.Majid tidak memuat \textit{cycle} ganjil sehingga $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Kemudian $G_2$ memiliki titik sebanyak $3j$ dan setiap titik di $G_2$ memiliki derajat $2j$. Oleh karena itu, $G_2$ memuat $C_{3j}$ sebagai \textit{cycle} maksimalnya. Berdasarkan definisi bilangan R-M-H yang merupakan bilangan positif terkecil sehingga $M_j(C_n,C_s) \leq 4$ untuk $j \geq2$, $n$ ganjil, dan $((s$ ganjil dengan $s < 2j)$ $ \text{atau} $ $(2j < s \leq 3j))$. ~\\\noindent\textbf{Kasus 2.} $G_1$ adalah \textit{matching}. ~\\\textit{Matching} $G_1$ pada graf $G$ adalah himpunan sisi dari graf $G$ yang saling lepas sehingga $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Banyak titik di $G_1$ adalah $4j$. Oleh karena itu, banyak titik di $G_1$ genap sehingga $G_1$ \textit{matching} sempurna. Jadi, setiap titik di $G_1$ memiliki derajat 1. Akibatnya, setiap titik di $G_2$ memiliki derajat $3j-1$, karena setiap titik di $G$ memiliki derajat $3j$. Oleh karena itu, $G_2$ memuat $C_{4j}$ sebagai \textit{cycle} maksimalnya. ~\\Dari \textbf{Kasus 1} dan \textbf{Kasus 2} diperoleh bahwa $G_2$ memuat \textit{cycle} $C_s$ untuk $s \leq4j$. Oleh karena itu, $G_2$ memuat $C_s$ untuk $((s$ ganjil dengan $s < 2j)$ $ \text{atau} $ $(2j < s \leq 3j))$. Akibatnya, $M_j(C_n,C_s) \leq 4$ untuk $j \geq2$, $n$ ganjil, dan $((s$ ganjil dengan $s < 2j)$ $ \text{atau} $ $(2j < s \leq 3j))$.\\ \noindent Berdasarkan hal di atas, diperoleh bahwa $M_j(C_n,C_s) \geq 4$ untuk $j \geq2$, $n$ ganjil, dan $((s$ ganjil dengan $s < 2j)$ $ \text{atau} $ $(2j < s \leq 3j))$ serta $M_j(C_n,C_s) \leq 4$ untuk $j \geq2$, $n$ ganjil, dan $((s$ ganjil dengan $s < 2j)$ $ \text{atau} $ $(2j < s \leq 3j))$. Oleh karena itu, $M_j(C_n,C_s) = 4$ untuk $j \geq2$, $n$ ganjil, dan $((s$ ganjil dengan $s < 2j)$ $ \text{atau} $ $(2j < s \leq 3j))$. \end{proof} \begin{theorem} \label{prop1} $M_j(C_n,C_s)= \lceil{ \frac{s}{j}} \rceil +1$ untuk $j \geq2$, $n$ ganjil, dan $s > 3j$. \end{theorem} \begin{proof} \\ Perhatikan hal-hal berikut ini: \begin{enumerate} \item[1.] Misalkan $M_j(C_n,C_s)= 5$ untuk $j \geq2$, $n$ ganjil, dan $3j < s \leq 4j$.\\ \noindent Pertama-tama akan ditunjukkan $M_j(C_n,C_s)\geq 5$ untuk $j \geq2$, $n$ ganjil, dan $3j < s \leq 4j$. Misalkan graf $F=K{(5-1) \times j}$. Beri $2-$pewarnaan merah-biru pada semua sisi graf $F$ sebagai berikut: warna merah untuk semua sisi $F_1$ dengan $F_1$ graf Majid $M_{4 \times j}$ dan warna biru pada semua sisi $F_2$ dengan $F_2 = \bar{F_1}$. Berdasarkan Definisi 3.1, $F_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Kemudian $F_2$ memiliki titik sebanyak $4j$ dan setiap titik memiliki derajat $3j$. Oleh karena itu, $F_2$ memuat $C_{3j}$ sebagai \textit{cycle} maksimalnya. Selanjutnya $F_2$ tidak mungkin memuat $C_s$ untuk $s > 3j$ karena $C_{3j}$ adalah \textit{cycle} maksimal $F_2$. Oleh karena itu, $M_j(C_n,C_s)\geq 5$ untuk $j \geq2$, $n$ ganjil, dan $s>3j$. Akibatnya, $M_j(C_n,C_s)\geq 5$ untuk $j \geq2$, $n$ ganjil, dan $3j < s \leq 4j$. \\ \noindent Selanjutnya akan ditunjukkan $M_j(C_n,C_s)\leq 5$ untuk $j \geq2$, $n$ ganjil, dan $3j < s \leq 4j$. Misalkan diberi $2-$pewarnaan merah-biru pada semua sisi graf $G = K_{5 \times j}$ sedemikian sehingga $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Akan ditunjukkan bahwa $G_2$ memuat $C_s$ biru untuk $3j < s \leq 4j$. Agar $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Perhatikan dua kasus berikut ini: ~\\\noindent \textbf{Kasus 1.} $G_1$ adalah graf A.Majid $M_{5 \times j}$. \noindent Perhatikan bahwa graf A.Majid tidak memuat \textit{cycle} ganjil sehingga $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Kemudian $G_2$ memiliki titik sebanyak $4j$ dan setiap titik di $G_2$ memiliki derajat $3j$. Oleh karena itu, $G_2$ memuat $C_{4j}$ sebagai \textit{cycle} maksimalnya. Berdasarkan definisi bilangan R-M-H yang merupakan bilangan positif terkecil sehingga $M_j(C_n,C_s)\leq 5$ untuk $j \geq2$, $n$ ganjil, dan $3j < s \leq 4j$. ~\\\noindent \textbf{Kasus 2.} $G_1$ adalah \textit{matching}. \noindent Perhatikan bahwa \textit{matching} $G_1$ pada graf $G$ adalah himpunan sisi dari graf $G$ yang saling lepas sehingga $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Kemudian $G_2$ memiliki titik sebanyak $5j$. Berdasarkan banyak titik di $G_1$, \textit{matching} $G_1$ dibagi menjadi 2 jenis: \begin{itemize} \item [\textbf{(a)}] Jika banyak titik di $G_1$ genap maka $G_1$ \textit{matching} sempurna. Oleh karena itu, setiap titik di $G_1$ memiliki derajat 1 sehingga setiap titik di $G_2$ memiliki derajat $4j-1$. Hal ini disebabkan setiap titik di $G$ memiliki derajat $2j$. Akibatnya, $G_2$ memuat \textit{cycle} dengan $C_{5j}$ adalah \textit{cycle} maksimalnya. \item[\textbf{(b)}] Jika banyak titik di $G_1$ ganjil maka $G_1$ \textit{matching} maksimal. Oleh karena itu, $\bigtriangleup(G_1)=1$ sehingga $\delta(G_2)=4j-1$. Hal ini disebabkan setiap titik di $G$ memiliki derajat $2j$. Akibatnya, $G_2$ memuat \textit{cycle} dengan $C_{5j}$ adalah \textit{cycle} maksimalnya. \noindent Dari \textbf{(a)} dan \textbf{(b)} diperoleh bahwa $G_2$ memuat \textit{cycle} dengan $C_{5j}$ adalah \textit{cycle} maksimalnya. \end{itemize} Dari \textbf{Kasus 1} dan \textbf{Kasus 2} diperoleh bahwa $G_2$ memuat \textit{cycle} $C_s$ untuk $s \leq5j$. Oleh karena itu, $G_2$ memuat $C_s$ untuk $3j < s \leq 4j$. Akibatnya, $M_j(C_n,C_s)\leq 5$ untuk $j \geq2$, $n$ ganjil, dan $3j < s \leq 4j$. ~\\\noindent Berdasarkan hal di atas, diperoleh bahwa $M_j(C_n,C_s)\geq 5$ untuk $j \geq2$, $n$ ganjil, dan $3j < s \leq 4j$ serta $M_j(C_n,C_s)\leq 5$ untuk $j \geq2$, $n$ ganjil, dan $3j < s \leq 4j$. Oleh karena itu, $M_j(C_n,C_s)= 5$ untuk $j \geq2$, $n$ ganjil, dan $3j < s \leq 4j$.\\ \item[2.] Misalkan $M_j(C_n,C_s)= 6$ untuk $j \geq2$, $n$ ganjil, dan $4j < s \leq 5j$.\\ \noindent Pertama-tama akan ditunjukkan $M_j(C_n,C_s)\geq 6$ untuk $j \geq2$, $n$ ganjil, dan $4j < s \leq 5j$. Misalkan graf $F=K{(6-1) \times j}$. Beri $2-$pewarnaan merah-biru pada semua sisi graf $F$ sebagai berikut: warna merah untuk semua sisi $F_1$ dengan $F_1$ graf Majid $M_{5 \times j}$ dan warna biru pada semua sisi $F_2$ dengan $F_2 = \bar{F_1}$. Berdasarkan Definisi 3.1, $F_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Kemudian $F_2$ memiliki titik sebanyak $4j$ dan setiap titik di $F_2$ memiliki derajat $3j$. Oleh karena itu, $F_2$ memuat $C_{4j}$ sebagai \textit{cycle} maksimalnya. Selanjutnya $F_2$ tidak mungkin memuat $C_s$ untuk $s > 4j$. Oleh karena itu, $M_j(C_n,C_s)\geq 6$ untuk $j \geq2$, $n$ ganjil, dan $s>4j$. Akibatnya, $M_j(C_n,C_s)\geq 6$ untuk $j \geq2$, $n$ ganjil, dan $4j < s \leq 5j$. ~\\\noindent Selanjutnya akan ditunjukkan $M_j(C_n,C_s)\leq 6$ untuk $j \geq2$, $n$ ganjil, dan $4j < s \leq 5j$. Misalkan diberi $2-$pewarnaan merah biru pada semua sisi graf $G = K_{6 \times j}$ sedemikian sehingga $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Akan ditunjukkan bahwa $G_2$ memuat $C_s$ biru untuk $4j < s \leq 5j$. Agar $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Perhatikan dua kasus berikut ini: ~\\\noindent \textbf{Kasus 1.} $G_1$ adalah graf A.Majid $M_{6 \times j}$. ~\\Perhatikan bahwa graf A.Majid tidak memuat \textit{cycle} ganjil sehingga $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Kemudian $G_2$ memiliki titik sebanyak $5j$ dan setiap titik di $G_2$ memiliki derajat $4j$. Oleh karena itu, $G_2$ memuat $C_{5j}$ sebagai \textit{cycle} maksimalnya. Berdasarkan definisi bilangan R-M-H yang merupakan bilangan positif terkecil sehingga $M_j(C_n,C_s)\leq 6$ untuk $j \geq2$, $n$ ganjil, dan $4j < s \leq 5j$. ~\\\noindent \textbf{Kasus 2.} $G_1$ adalah \textit{matching}. ~\\Perhatikan bahwa \textit{matching} $G_1$ pada graf $G$ adalah himpunan sisi dari graf $G$ yang saling lepas sehingga $G_1$ tidak memuat $C_n$ merah untuk $n$ ganjil. Banyak titik di $G_1$ sebanyak $6j$. Oleh karena itu, banyak titik di $G_1$ adalah genap sehingga $G_1$ \textit{matching} sempurna. Jadi, setiap titik di $G_1$ memiliki derajat 1. Akibatnya, setiap titik di $G_2$ memiliki derajat $5j-1$, karena setiap titik di $G$ memiliki derajat $5j$. Oleh karena itu, $G_2$ memuat $C_{6j}$ sebagai \textit{cycle} maksimalnya. ~\\\noindent Dari \textbf{Kasus 1} dan \textbf{Kasus 2} diperoleh bahwa $G_2$ memuat $C_s$ untuk $s \leq5j$. Oleh karena itu, $G_2$ memuat $C_s$ untuk $4j < s \leq 5j$. Akibatnya, $M_j(C_n,C_s)\leq 6$ untuk $j \geq2$, $n$ ganjil, dan $4j < s \leq 5j$. ~\\\noindent Berdasarkan hal di atas, diperoleh bahwa $M_j(C_n,C_s)\geq 6$ untuk $j \geq2$, $n$ ganjil, dan $4j < s \leq 5j$ serta $M_j(C_n,C_s)\leq 6$ untuk $j \geq2$, $n$ ganjil, dan $4j < s \leq 5j$. Oleh karena itu, $M_j(C_n,C_s) = 6$ untuk $j \geq2$, $n$ ganjil, dan $4j < s \leq 5j$. \item[3.] Selanjutnya hal yang sama dilakukan untuk $j \geq2$, $n$ ganjil, dan $s > 5j$. ~\\\noindent Berdasarkan hal-hal di atas, terdapat pola $M_j(C_n,C_s)$ untuk $j \geq2$, $n$ ganjil dan $s>3j$ sebagai berikut. \begin{enumerate} \item[1.] $M_j(C_n,C_s)= 5$ untuk $3j < s \leq 4j$. \item[2.] $M_j(C_n,C_s)= 6$ untuk $4j < s \leq 5j$. \item[3.] Dan seterusnya dengan pola $M_j(C_n,C_s)= y$ untuk $(y-2)j < s \leq (y-1)j$ dengan $y \geq7$. \end{enumerate} ~\\\noindent Akibatnya, diperoleh $M_j(C_n,C_s)= \lceil{ \frac{s}{j}} \rceil +1$ untuk $j \geq2$, $n$ ganjil, dan $s > 3j$. \end{enumerate} \end{proof} \section{Kesimpulan} Pada penelitian ini, telah ditentukan bilangan R-M-H $M_j (C_n,C_s)$ untuk \textit{cycle}. Berikut ini adalah hasil yang diperoleh pada penelitian ini: ~\\\noindent Bilangan R-M-H $M_j (C_n,C_s)$ untuk $j \geq2$, $n$ ganjil, dan $s \geq 3$ adalah $M_j(C_n,C_s)=$ $\begin{cases} 3 &; s \text{ genap dengan } s \leq2j, \\ 4&; (s \text { ganjil dengan } s < 2j) \text{ atau }(2j < s \leq 3j), \\ \lceil{ \frac{s}{j}} \rceil +1 &; s > 3j.\\ \end{cases}$ \section{Ucapan Terima kasih} Penulis mengucapkan terima kasih kepada Ibu Des Welyyanti, Bapak Muhafzan, dan Ibu Haripamyu yang telah memberikan masukan dan saran sehingga artikel ini dapat diselesaikan dengan baik. \begin{thebibliography}{0} \bibitem{1} Bondy, J. A. and U.S.R. Murty. 2008. \textit{Graph Theory}. Graduated Text in Mathematics, New York. \bibitem{2} Burger, A. P and J. H. van Vuuren. 2004. Ramsey Numbers In Complete Balance Multipartite Graphs Part I: Set Numbers. \textit{Discrete Math}. 283: (37-43). \bibitem{3} Burger, A. P and J. H. van Vuuren. 2004. Ramsey Numbers In Complete Balance Multipartite Graphs Part II: Size Numbers. \textit{Discrete Math}. 283: (45-49). \bibitem{4} Goddard, W, A. H. Michael, and R. O, Ortrud. 2000. Bipartite Ramsey Numbers and Zarankiewiez Numbers. \textit{Discrete Mathematics}. 219:85-95. \bibitem{5} Kalbeisch J. G. 1966. \textit{Chromatic Graphs and Ramsey's Theorem}, Ph. D Thesis, University of Waterloo, Kanada. \bibitem{6} Lubis A. A. 2021. Bilangan Ramsey Multipartit Himpunan untuk Kombinasi Graf Lintasan dengan Graf Roda $M_4(P_3,W_n)$ dengan $n \leq 3$. \textit{Skripsi: Jurusan Matematika Universitas Andalas, Padang}. \bibitem{7} Syafrizal Sy, A. S. Zain. 2021. The Set Multipartit Ramsey Number. \textit{Jurusan Matematika Universitas Andalas}, Padang. \end{thebibliography} \end{document}