\documentclass{template-jurnal} %Bagian ini diedit oleh editor Jurnal Matematika UNAND

%Perhatikan aturan penulisan dan ukuran huruf yang digunakan
\begin{document}

\markboth{Nadya Citra Multasya dkk}{Bilangan R-M-H untuk Graf Lintasan $P_4$ dan Graf Roda $W_n$ dengan $n \geq 3$}

%%%%%%%%%%%%%%%%%%%%% Publisher's Area please ignore %%%%%%%%%%%%%%%
%
\catchline{}{}{}{}{}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{BILANGAN R-M-H UNTUK GRAF LINTASAN $P_4$ DAN GRAF RODA $W_n$ DENGAN $n \geq 3$}

\author{NADYA CITRA MULTASYA\footnote{Corresponding author}  , MAHDHIVAN SYAFWAN, SYAFRIZAL SY}

\address{Program Studi S1 Matematika,\\
Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Andalas,\\
Kampus UNAND Limau Manis Padang, Indonesia.\\
email : \email{nacit.multasya@gmail.com, mahdhivan@sci.unand.ac.id, syafrizalsy@sci.unand.ac.id}}

\maketitle
\setcounter{page}{1} %bagian ini diedit oleh editor Jurnal Matematika UNAND

\begin{abstract}

\noindent
\textbf{Abstrak}. 
Diberikan dua graf $G$ dan $H$ serta bilangan asli $j \geq 2$. Bilangan Ramsey multipartit himpunan (R-M-H) $M_j(G,H)$ adalah suatu bilangan bulat positif terkecil $t$ sedemikian sehingga untuk sebarang faktorisasi $K_{(t \times j)} \cong F_1 \oplus F_2$ senantiasa $F_1$ memuat subgraf $G$ atau $F_2$ memuat subgraf $H$. Pada artikel ini akan ditentukan $M_3(P_4,W_n)$ dimana $P_4$ adalah suatu graf lintasan yang terdiri dari 4  simpul dan $W_n$ adalah suatu graf roda yang terdiri dari $n+1$ simpul dengan $n\geq 3$.
\end{abstract}

\keywords{\emph{Bilangan R-M-H, graf lintasan, graf roda}}

\section{Pendahuluan}
Teori Ramsey pertama kali diperkenalkan oleh Frank Plumpton Ramsey dalam makalahnya yang berjudul $^{"}$On a problem of formal logic$^{"}$ pada tahun 1928 \cite{Ramsey}. Ide dasar dari teori yang dikenal dengan teori Ramsey ini adalah bilangan Ramsey klasik. Jika diberikan dua bilangan asli $m$ dan $n$, maka didefinisikan bilangan Ramsey $r(m,n)$ sebagai bilangan bulat positif terkecil $p$ sedemikian sehingga jika graf lengkap $K_p$ diberi 2-pewarnaan merah dan biru pada setiap sisinya, maka akan selalu terdapat graf lengkap $K_m$ merah atau graf lengkap $K_n$ biru sebagai subgraf dari $K_p$ \cite{Clark}. Hingga saat ini, baru ditemukan sembilan bilangan Ramsey klasik, yaitu $r(3,3)=6$, $r(3,4)=9$, $r(3,5)=14$, $r(3,6)=18$, $r(3,7)=23$, $r(3,8)=28$, $r(3,9)=36$, $r(4,4)=18$, dan $r(4,5)=25$ \cite{Radziszowski}.

~\\ Kajian bilangan Ramsey diperluas untuk dua graf sebarang. Misalkan diberikan \linebreak sebarang graf $F$ dan $H$. Bilangan Ramsey $r(F,H)$ didefinisikan sebagai suatu \linebreak bilangan asli terkecil $n$ sedemikian sehingga jika graf lengkap $K_n$ diberi sebarang \linebreak pewarnaan merah-biru pada setiap sisinya, maka graf lengkap $K_n$ akan selalu memuat subgraf berwarna merah yang isomorfik dengan $F$ atau subgraf berwarna biru yang isomorfik dengan $H$ \cite{Chartrand}. Bilangan Ramsey pun dikembangkan untuk \linebreak kasus dua partit dan dinamakan bilangan Ramsey bipartit. Bilangan Ramsey \linebreak bipartit kemudian diperumum menjadi bilangan Ramsey multipartit. Pada awal abad ke-21, Burger dan Vuuren mengkaji bilangan Ramsey multipartit dan mempublikasikan hasilnya dalam jurnal berjudul "Ramsey numbers in complete balanced graphs". Kedua ahli matematika ini membagi jurnal tersebut menjadi dua bagian. Jurnal bagian pertama membahas bilangan Ramsey multipartit himpunan (R-M-H) \cite{Burger1} dan bagian kedua membahas bilangan Ramsey multipartit ukuran (R-M-U) \cite{Burger2}. 

~\\ Pada tahun 2020, Yuri \cite{Yuri} telah menentukan rumus untuk bilangan \linebreak R-M-H $M_2(P_n,W_s)$ dengan $n=3$, $n=4$, dan $s \geq 3$. Setahun setelahnya, \linebreak Lubis \cite{Lubis} mengkaji bilangan R-M-H kombinasi graf lintasan $P_3$ dengan graf roda $W_n
$ untuk $n \geq 3$ dan $j=4$ dalam skripsinya. Oleh karena itu, penulis tertarik untuk mengkaji bilangan R-M-H kombinasi graf lintasan dengan graf roda. Adapun graf yang peneliti kaji dalam artikel ini adalah graf lintasan $P_4$ dan graf roda $W_n$.

\section{Landasan Teori}
\noindent
Suatu subgraf dari graf $G$ yang himpunan simpulnya $U \subseteq V(G)$ dan himpunan sisinya adalah semua sisi dari graf $G$ yang mengaitkan dua simpul di $U$ \linebreak  dinamakan \textbf{subgraf terinduksi} dan dinotasikan dengan $G[U]$ \cite{Wallis}. Graf $G$ dan $H$ \textbf{isomorfik} jika terdapat suatu fungsi bijektif $\phi : V(G) \to V(H)$ sedemikian \linebreak sehingga simpul $u$ dan $v$ bertetangga pada $G$ jika dan hanya jika $\phi(u)$ dan $\phi(v)$ bertetangga di $H$. \textbf{Siklus Hamilton} adalah suatu lintasan tertutup yang semua simpul dilewati tepat satu kali. Berikut beberapa teorema terkait siklus Hamilton yang akan digunakan pada artikel ini.

\begin{theorem}  \emph{\cite{Chartrand}} \textbf{(Teorema Dirac)}
Jika $G$ adalah graf dengan kardinalitas \linebreak simpul $n \geq 3$ dan $\delta(G) \geq \frac{n}{2}$, maka $G$ memuat siklus Hamilton. 
\end{theorem}

\begin{theorem}  \emph{\cite{Chartrand}} \textbf{(Teorema Ore)}
Misalkan $G$ adalah graf dengan orde $n \geq 3$ dan $\sigma_2(G)$ menyatakan jumlah derajat minimum dari dua simpul yang tidak bertetangga di G. Jika $\sigma_2(G) \geq n$, maka $G$ memuat siklus Hamilton. 
\end{theorem}

~\\ \textbf{Graf lintasan} adalah graf terhubung sederhana yang simpulnya dapat disusun dalam suatu barisan sedemikian sehingga dua simpulnya bertetangga jika kedua simpul tersebut berurutan dalam barisan tersebut \cite{Bondy}. Graf lintasan $P_n$ memiliki $n$ simpul dan $n-1$ sisi dengan $n \geq 1$ \cite{Chartrand}. Graf lingkaran adalah graf terhubung sederhana yang semua simpulnya berderajat 2. \textbf{Graf roda} merupakan suatu graf terhubung sederhana yang memuat graf lingkaran ditambah satu simpul pusat yang bertetangga dengan semua simpul pada graf lingkaran tersebut. Graf ini memiliki $n+1$ simpul dan $2n$ sisi dengan $n \geq 3$ dan dinotasikan sebagai $W_n$. \textbf{Graf multipartit} adalah graf yang semua simpulnya dapat dipartisi ke dalam $k$ himpunan partit dengan syarat setiap simpul yang berada di partit yang sama tidak bertetangga. Graf 2-partit disebut juga graf bipartit. Graf multipartit seimbang lengkap $K_{(t \times j)}$ adalah setiap simpul bertetangga dengan setiap simpul pada partit lainnya dan tidak bertetangga dengan simpul pada partit yang sama dan kardinalitas simpul pada setiap himpunan partitnya sama yaitu $j$. \textbf{Graf bintang} $S_m$ adalah graf bi-\linebreak partit lengkap dimana kardinalitas simpul salah satu partitnya adalah 1 (dinamakan simpul pusat) dan m selainnya.

\begin{theorem}  \emph{\cite{Bondy}}
Suatu graf $G$ dikatakan bipartit jika dan hanya jika  graf $G$ tidak memuat siklus ganjil.
\end{theorem}

~\\ Pada tahun 2004, Burger dan Vuuren mendefinisikan bilangan R-M-H sebagai berikut.

\begin{definition} \emph{\cite{Burger1}}
Misalkan $K_{(\zeta \times j)}$ adalah suatu graf multipartit seimbang lengkap yang terdiri dari $\zeta$ himpunan partit dan $j$ banyaknya simpul pada setiap himpunan partit. Misalkan $j,l,n,s,$ dan $t$ adalah bilangan-bilangan bulat positif dengan $n,s \geq 2$. Bilangan R-M-H $M_j (K_{(n \times l)}, K_{(s \times t)})$ adalah bilangan bulat positif terkecil $\zeta$ sedemikian sehingga sebarang pewarnaan dari sisi $K_{(\zeta \times j)}$ menggunakan dua warna merah dan biru, maka mestilah  $K_{(\zeta \times j)}$ ini memuat  $K_{(n \times l)}$ merah atau $K_{(s \times t)}$ biru sebagai subgraf.
\end{definition}

~\\ Selanjutnya, Definisi 2.4 diperumum untuk kombinasi dua graf sebarang yang tidak harus lengkap dan didefinisikan sebagai berikut.

\begin{definition}
Diberikan dua graf $G$ dan $H$, dan bilangan asli $j \geq 2$. Bilangan R-M-H $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 pewarnaan merah-biru, maka graf $K_{(t \times j)}$ akan memuat subgraf $G$ berwarna merah atau subgraf $H$ berwarna biru.
\end{definition}

~\\ Definisi 2.5 ekuivalen dengan definisi berikut.

\begin{definition} 
Diberikan dua graf $G$ dan $H$, dan bilangan asli $j \geq 2$. Bilangan R-M-H $M_j(G,H)$ adalah bilangan bulat positif terkecil $t$ sedemikian sehingga untuk sebarang faktorisasi $K_{(t \times j)} \cong F_1 \oplus F_2$ maka senantiasa $F_1$ memuat subgraf $G$ atau $F_2$ memuat subgraf $H$.
\end{definition}

\section{Bilangan R-M-H untuk $P_4$ dan $W_n$ dengan $n \geq 3$}

\noindent Berdasarkan Definisi 2.6, bilangan R-M-H $M_3(P_4,W_n)$ didefinisikan sebagai \linebreak suatu bilangan asli terkecil $t$ sedemikian sehingga untuk sebarang faktorisasi $H = K_{(t \times 3)} \cong F \oplus G$ akan selalu terdapat $F$ yang memuat $P_4$ atau $G$ yang memuat $W_n$ sebagai subgraf dari $H$. Artikel ini menggunakan istilah \textit{hub} sebagai simpul pusat dari graf roda $W_n$ dan \textit{pusat} sebagai simpul pusat dari graf bintang $S_m$. Berikut disajikan teorema-teorema untuk menentukan bilangan R-M-H $M_3(P_4,W_n)$.

\begin{theorem}
$M_3(P_4,W_n) = 4$ untuk $n \in \{4,6\}$.
\end{theorem}

\begin{proof} 
~\\ Pertama akan ditunjukkan $M_3(P_4,W_n)\geq 4$. Misalkan graf $F = K_{((4 - 1) \times 3)} \cong F_1 \oplus F_2$. Pilih $F_1 = 3C_3$. Jelas bahwa $F_1 \nsupseteq P_4$. Misalkan $V_i = \{v_{i,1}, v_{i,2}, v_{i,3}\}$ untuk $i = 1,2,3$ adalah himpunan partit di $F$. Pandang simpul $x$ yang \linebreak berada di partit $V_j$ sebagai \textit{hub} di $F_2$. Misalkan $H$ adalah himpunan simpul yang bertetangga dengan $x$ di $F_1$. Perhatikan bahwa $\Delta(F_2[V(F) \setminus (V_j \cup H)]) \leq 1$, sehingga tidak mungkin subgraf terinduksi $F_2[V(F) \setminus (V_j \cup H)]$ memuat $C_n$. \linebreak Akibatnya $F_2 \nsupseteq W_n$ sebagai subgraf dari $F$. Oleh karena itu, haruslah $M_3(P_4,W_n) \geq 4$.

~\\ Selanjutnya akan ditunjukkan $M_3(P_4,W_n) \leq 4$. Misalkan graf $G = K_{(4 \times 3)} \cong G_1 \oplus G_2$. Identifikasi semua kasus $G_1$ yang tidak memuat $P_4$. Akan ditunjukkan $G_2$ memuat $W_n$. Misalkan $V_i = \{v_{i,1}, v_{i,2}, v_{i,3}\}$ untuk $i = 1,2,3,4$ adalah himpunan partit di $G$. Berikut kasus-kasus untuk $G_1 \nsupseteq P_4$.

~\\ \textbf{Kasus 1.} $G_1 = 4C_3$.

\noindent
Jelas bahwa $G_1 \nsupseteq P_4$. Selanjutnya pandang suatu simpul $x$ pada partit $V_j$ sebagai \textit{hub} di $G_2$. Misalkan $H$ adalah himpunan simpul yang bertetangga dengan $x$ di $G_1$. Berdasarkan Teorema 2.1, subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ dengan $7$ simpul dan $\delta(G_2[V(G) \setminus (V_j \cup H)]) \geq 4 > \frac{7}{2}$ memuat siklus Hamilton, artinya $G_2[V(G) \setminus (V_j \cup H)]$ memuat $C_n$ dengan $n \leq 7$. Karena terdapat simpul $x$ pada partit $V_j$ sebagai \textit{hub} dan subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ membentuk $C_n$, maka jelas bahwa $G_2 \supseteq W_n$ sebagai subgraf dari $G$.

~\\ \textbf{Kasus 2.} $G_1$ adalah hutan.

\noindent 
Misalkan $G_1$ adalah hutan yang komponennya graf bintang $n_iS_{m_i}$ untuk $i=1,2,3,\dotsb,12$ dengan $0 \leq m_i \leq 9$, $n_i \geq 0$,  dan $\sum_{i=1}^{12} n_im_i = 12$. Jelas bahwa $G_1 \nsupseteq P_4$. Kasus ini dibagi menjadi dua subkasus sebagai berikut.

~\\ \textbf{Subkasus 2.1.} $G_1 = 3S_4$ dimana setiap \textit{pusat} berada di partit $V_k$ dan setiap daun dari masing-masing graf bintang $S_4$ berada di suatu partit $V_j$ dengan $j \ne k$.

\noindent 
Misalkan partit $V_k$ memuat \textit{pusat}. Perhatikan bahwa derajat setiap simpul pada $V_k$ lebih besar dibandingkan derajat simpul pada $G_1 \setminus V_k$. Oleh karena itu, simpul pada $V_k$ tidak dapat dijadikan \textit{hub} di $G_2$ dan \textit{hub} mestilah berada di $G_2 \setminus V_k$. Pandang suatu simpul $x$ pada $V_j$ sebagai \textit{hub} di $G_2$. Misalkan $H$ adalah himpunan simpul yang bertetangga dengan $x$ di $G_1$. Perhatikan bahwa $\delta(G_2[V(G) \setminus (V_j \cup H)]) \geq 4$. Berdasarkan Teorema 2.2, subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ dengan $8$ simpul dan $\sigma_2(G_2[V(G) \setminus (V_j \cup H)]) \geq 9 > 8$ memuat siklus Hamilton, artinya $G_2[V(G) \setminus (V_j \cup H)]$ memuat $C_n$ dengan $n \leq 8$. Perhatikan
bahwa subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ isomorfik dengan graf bipartit $K_{(2 \times 4)}$. Berdasarkan Teorema 2.3, $G_2[V(G) \setminus (V_j \cup H)]$ tidak memuat siklus ganjil. Oleh karena itu, $G_2[V(G) \setminus (V_j \cup H)]$ hanya memuat $C_n$ untuk $n \in \{4,6,8\}$. Karena terdapat simpul $x$ pada partit $V_j$ sebagai \textit{hub} dan subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ membentuk $C_n$, maka jelas bahwa $G_2 \supseteq W_n$ sebagai subgraf dari $G$. Ilustrasi subkasus ini dapat dilihat pada Gambar 1 berikut.\\[0.25ex]

\begin{figure}[htbp]
	\begin{center}
		\includegraphics[scale=0.33]{teorema1kasus21}
		\caption{(a) $G = K_{(4 \times 3)}$, (b) $G_1 = 3S_4 \nsupseteq P_4$, (c) $G_2 \supseteq W_n$}
	\end{center}
\end{figure}

~\\ \textbf{Subkasus 2.2.} $G_1 \neq 3S_4$ yang setiap \textit{pusat} berada di partit $V_k$ dan setiap daun dari masing-masing graf bintang $S_4$ berada di suatu partit $V_j$ dengan $j \ne k$.

\noindent 
Pilih simpul $x$ pada partit $V_j$ yang terkait dengan \textit{pusat} dari $max\{S_{mi}\}$, sedemikian sehingga $V_j$ merupakan partit dengan jumlah derajat ketiga simpulnya maksimal di $G_1$. Pandang simpul $x$ ini sebagai \textit{hub} di $G_2$. \linebreak Misalkan $H$ adalah himpunan simpul yang bertetangga dengan $x$ di $G_1$. Perhatikan bahwa $\delta(G_2[V(G) \setminus (V_j \cup H)]) \geq 4$. Berdasarkan Teorema 2.2, subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ dengan $8$ simpul dan $\sigma_2(G_2[V(G) \setminus (V_j \cup H)]) \geq 9 > 8$ memuat siklus Hamilton, artinya $G_2[V(G) \setminus (V_j \cup H)]$ memuat $C_n$ dengan $n \leq 8$. Karena \linebreak terdapat simpul $x$ pada partit $V_x$ sebagai \textit{hub} dan subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ membentuk $C_n$, maka jelas bahwa $G_2 \supseteq W_n$ sebagai subgraf dari $G$.

~\\ Dari \textbf{kasus 1}, \textbf{subkasus 2.1}, dan \textbf{subkasus 2.2}, diperoleh $G_2 \supseteq W_n$ sebagai subgraf dari $G$. Oleh karena itu, haruslah $M_3(P_4,W_n) \leq 4$.

~\\ Dengan demikian, disimpulkan $M_3(P_4,W_n) = 4$ untuk $n \in \{4,6\}$.
\end{proof}

\begin{theorem}
$M_3(P_4,W_n) = 5$ untuk $n \in \{3,5,7,8,9,10\}.$
\end{theorem}

\begin{proof}
~\\ Pertama akan ditunjukkan $M_3(P_4,W_n) \geq 5$. Misalkan graf $F = K_{((5 - 1) \times 3)} \cong F_1 \oplus F_2$. Misalkan $V_i = \{v_{i,1}, v_{i,2}, v_{i,3}\}$ untuk $i = 1,2,3,4$ adalah himpunan partit di $F$. Berikut beberapa kasus untuk $F_1 \nsupseteq P_4$.

~\\ \textbf{Kasus 1.} $F_1 = 4C_3$.

\noindent 
Jelas bahwa $F_1 \nsupseteq P_4$. Selanjutnya pandang suatu simpul $x$ pada partit $V_j$ sebagai \textit{hub} di $F_2$. Misalkan $H$ adalah himpunan simpul yang bertetangga dengan $x$ di $F_1$. Berdasarkan Teorema 2.1, subgraf terinduksi $F_2[V(F) \setminus (V_j \cup H)]$ dengan $7$ simpul dan $\delta(F_2[V(F) \setminus (V_j \cup H)]) \geq 4 > \frac{7}{2}$ memuat siklus Hamilton, artinya $F_2[V(F) \setminus (V_j \cup H)]$ memuat $C_n$ dengan $n \leq 7$ dan tidak memuat $C_n$ untuk $n > 7$. Akibatnya $F_2 \nsupseteq W_n$.

~\\
\textbf{Kasus 2.} $F_1 = 3S_4$ dimana setiap \textit{pusat} berada di partit $V_k$ dan setiap daun dari masing-masing graf bintang $S_4$ berada di suatu partit $V_j$ dengan $j \ne k$.

\noindent
Jelas bahwa $F_1 \nsupseteq P_4$. Selanjutnya perhatikan bahwa derajat setiap simpul pada $V_k$ lebih besar dibandingkan derajat simpul pada $F_1 \setminus V_k$. Oleh karena itu, simpul pada $V_k$ tidak dapat dijadikan \textit{hub} di $F_2$ dan \textit{hub} mestilah berada di $F_2 \setminus V_k$. Pandang suatu simpul $x$ pada $V_j$ sebagai \textit{hub} di $F_2$. Misalkan $H$ adalah himpunan simpul yang bertetangga dengan $x$ di $F_1$. Perhatikan bahwa $\delta(F_2[V(F) \setminus (V_j \cup H)]) \geq 4$. Berdasarkan Teorema 2.2, subgraf terinduksi $F_2[V(F) \setminus (V_j \cup H)])$ dengan $8$ simpul dan $\sigma_2(F_2[V(F) \setminus (V_j \cup H)]) \geq 9 > 8$ memuat siklus Hamilton, artinya $F_2[V(F) \setminus (V_j \cup H)]$ memuat $C_n$ dengan $n \leq 8$. Perhatikan subgraf terinduksi $F_2[V(F) \setminus (V_j \cup H)]$ isomorfik dengan graf bipartit $K_{(2 \times 4)}$. Menurut Teorema 2.3, $F_2[V(F) \setminus (V_j \cup H)]$ tidak memuat siklus ganjil. Oleh karena itu, graf $F_2[V(F) \setminus (V_j \cup H)]$ hanya memuat $C_n$ untuk $n \in \{4,6,8\}$ dan tidak memuat $C_n$ untuk $n \in \{3,5,7\}$. Akibatnya $F_2 \nsupseteq W_n$.

~\\ Dari \textbf{kasus 1} dan \textbf{kasus 2}, diperoleh $F_2 \nsupseteq W_n$ sebagai subgraf dari $F$. Oleh karena itu, haruslah $M_3(P_4,W_n)$ $\geq 5$.

~\\ Selanjutnya akan ditunjukkan $M_3(P_4,W_n) \leq 5$. Misalkan graf $G = K_{(5 \times 3)} \cong G_1 \oplus G_2$. Identifikasi semua kasus $G_1$ yang tidak memuat $P_4$. Akan ditunjukkan $G_2$ memuat $W_n$. Misalkan $V_i = \{v_{i,1}, v_{i,2}, v_{i,3}\}$ untuk $i = 1,2,3,4,5$ adalah \linebreak himpunan partit di $G$. Berikut kasus-kasus untuk $G_1 \nsupseteq P_4$.

~\\ \textbf{Kasus 1.} $G_1 = 5C_3$.

\noindent 
Jelas bahwa $G_1 \nsupseteq P_4$. Selanjutnya pandang suatu simpul $x$ pada partit $V_j$ sebagai \textit{hub} di $G_2$. Misalkan $H$ adalah himpunan simpul yang bertetangga dengan $x$ di $G_1$. Berdasarkan Teorema 2.1, subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ dengan $10$ simpul dan $\delta(G_2[V(G) \setminus (V_j \cup H)]) \geq 7 > \frac{10}{2}$ memuat siklus Hamilton, artinya $G_2[V(G) \setminus (V_j \cup H)]$ memuat $C_n$ dengan $n \leq 10$. Karena terdapat simpul $x$ pada partit $V_j$ sebagai \textit{hub} dan subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ membentuk $C_n$, maka jelas bahwa $G_2 \supseteq W_n$ sebagai subgraf dari $G$.

~\\ \textbf{Kasus 2.} $G_1$ adalah hutan yang komponennya graf bintang $n_iS_{m_i}$ untuk $i=1,2,3,\dotsb,15$ dengan $0 \leq m_i \leq 12$, $n_i \geq 0$,  dan $\sum_{i=1}^{15} n_im_i = 15$.

\noindent
Jelas bahwa $G_1 \nsupseteq P_4$. Selanjutnya pilih simpul $x$ pada partit $V_j$ yang terkait dengan \textit{pusat} dari $max\{S_{mi}\}$ sedemikian sehingga $V_j$ merupakan partit dengan jumlah derajat ketiga simpulnya maksimal di $G_1$. Pandang simpul $x$ ini sebagai \textit{hub} di $G_2$. Misalkan $H$ adalah himpunan simpul yang bertetangga dengan $x$ di $G_1$. Perhatikan bahwa $\delta(G_2[V(G) \setminus (V_j \cup H)]) \geq 5$. Berdasarkan Teorema 2.2, subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ dengan $11$ simpul dan $\sigma_2(G_2[V(G) \setminus (V_j \cup H)]) \geq 11 = 11$ memuat siklus Hamilton, artinya $G_2[V(G) \setminus (V_j \cup H)]$ memuat $C_n$ dengan $n \leq 11$. Karena terdapat simpul $x$ pada partit $V_j$ sebagai \textit{hub} dan subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ membentuk $C_n$, maka jelas bahwa $G_2 \supseteq W_n$ sebagai subgraf dari $G$.

~\\ Dari \textbf{kasus 1} dan \textbf{kasus 2}, diperoleh $G_2 \supseteq W_n$ sebagai subgraf dari $G$. Oleh karena itu, haruslah $M_3(P_4,W_n) \leq 5$.

~\\ Dengan demikian, disimpulkan $M_3(P_4,W_n) = 5$ untuk $n \in \{3,5,7,8,9,10\}$.
\end{proof}

~\\ Teorema berikut untuk menentukan bilangan R-M-H untuk graf lintasan $P_4$ dan graf roda $W_n$ dengan $n \geq 11$. 

\begin{theorem}
$M_3(P_4,W_n) = \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil$ untuk $n \geq 11$.
\end{theorem}

\begin{proof}
~\\ Pertama-tama akan ditunjukkan $M_3(P_4,W_n) \geq \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil$. Misalkan graf $F = K_{((\lceil \frac{n+5}{3} \rceil - 1) \times 3)} \cong F_1 \oplus F_2$. Pilih $F_1 = \Big( \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil - 1 \Big) C_3$. Jelas bahwa $F_1 \nsupseteq P_4$. Misalkan $V_i = \{v_{i,1}, v_{i,2}, v_{i,3}\}$ untuk $i = 1,2,3,\dotsb,\Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil - 1$ adalah himpunan partit di $F$. Pandang suatu simpul $x$ pada partit $V_j$ \linebreak sebagai \textit{hub} di $F_2$. Misalkan $H$ adalah himpunan simpul yang bertetangga dengan $x$ di $F_1$. Berdasarkan Teorema 2.1, subgraf terinduksi $F_2[V(F) \setminus (V_j \cup H)]$ dengan $3 \Big( \Big( \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil - 1 \Big) - 1 \Big)$ simpul dan $\delta(F_2[V(F) \setminus (V_j \cup H)]) \geq 3 \Big( \Big( \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil - 1 \Big) - 1 \Big) - 2 \geq 3 \Big( \Big( \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil - 1 \Big) - 1 \Big) \Big \slash 2$ memuat siklus Hamilton, artinya $F_2[V(F) \setminus (V_j \cup H)]$ memuat $C_n$ dengan $n \leq 3 \Big( \Big( \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil - 1 \Big) - 1 \Big) - 2$. Perhatikan bahwa untuk mem-\linebreak bentuk $C_n$ dibutuhkan minimal $n$ simpul, sedangkan pada $F_2[V(F) \setminus (V_j \cup H)]$ ter-\linebreak dapat $3 \Big( \Big( \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil - 1 \Big) - 1 \Big) - 2 < n$ simpul untuk $n \geq 11$. Akibatnya $F_2 \nsupseteq W_n$ sebagai subgraf dari $F$. Oleh karena itu, haruslah $M_3(P_4,W_n) \geq \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil$.

~\\ Selanjutnya, akan ditunjukkan $M_3(P_4,W_n) \leq \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil$. Misalkan graf $G = K_{(\lceil \frac{n+5}{3} \rceil \times 3)} \cong G_1 \oplus G_2$. Identifikasi semua kasus $G_1$ yang tidak memuat $P_4$. Akan ditunjukkan $G_2$ memuat $W_n$. Misalkan $V_i = \{v_{i,1}, v_{i,2}, v_{i,3}\}$ untuk $i = 1,2,3,\dotsb,\Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil$ adalah himpunan partit di $G$. Berikut kasus-kasus untuk $G_1 \nsupseteq P_4$.

~\\ \textbf{Kasus 1.} $G_1 = \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil C_3$.

\noindent Jelas bahwa $G_1 \nsupseteq P_4$. Selanjutnya pandang suatu simpul $x$ pada partit $V_j$ \linebreak sebagai \textit{hub} di $G_2$. Misalkan $H$ adalah himpunan simpul yang bertetangga \linebreak dengan $x$ di $G_1$. Berdasarkan Teorema 2.1, subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ dengan $3 \Big( \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil - 1 \Big)$ simpul dan $\delta(G_2[V(G) \setminus (V_j \cup H)]) \geq 3 \Big( \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil - 1 \Big) - 2 \geq 3 \Big( \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil - 1 \Big) \Big \slash 2$ untuk $n \geq 11$ memuat siklus Hamilton, artinya $G_2[V(G) \setminus (V_j \cup H)]$ memuat $C_n$. Karena terdapat simpul $x$ pada partit $V_j$ \linebreak sebagai \textit{hub} dan subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ membentuk $C_n$, maka jelas bahwa $G_2 \supseteq W_n$ sebagai subgraf dari $G$.

~\\ \textbf{Kasus 2.} $G_1$ adalah hutan yang komponennya graf bintang $n_iS_{m_i}$ untuk $i=1,2,3,\dotsb,\Bigl \lceil \frac{n+5}{3} \Bigr \rceil$ dengan $0 \leq m_i \leq 3 \Big( \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil - 1 \Big)$, $n_i \geq 0$, dan $\sum_{i=1}^{3 \lceil \frac{n+5}{3} \rceil} n_im_i = 3\Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil$.

\noindent
Jelas bahwa $G_1 \nsupseteq P_4$. Selanjutnya pilih simpul $x$ pada partit $V_j$ yang terkait dengan \textit{pusat} dari $max\{S_{mi}\}$ sedemikian sehingga $V_j$ merupakan partit dengan jumlah derajat ketiga simpulnya maksimal di $G_1$. Pandang simpul $x$ ini sebagai \textit{hub} di $G_2$. Misalkan $H$ adalah himpunan \linebreak simpul yang bertetangga dengan $x$ di $G_1$. Perhatikan bahwa $\delta(G_2[V(G) \setminus (V_j \cup H)]) \geq \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil$. Berdasarkan Teorema 2.2, subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ \linebreak dengan $3 \Big( \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil - 1 \Big)$ simpul dan $\sigma_2(G_2[V(G) \setminus (V_j \cup H)]) \geq 2\Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil + 1 \geq 3 \Big( \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil - 1 \Big)$ untuk $n \geq 11$ memuat siklus Hamilton, artinya $G_2[V(G) \setminus (V_j \cup H)]$ memuat $C_n$. Karena terdapat simpul $x$ pada partit $V_j$ sebagai \textit{hub} dan subgraf terinduksi $G_2[V(G) \setminus (V_j \cup H)]$ membentuk $C_n$, maka jelas bahwa $G_2 \supseteq W_n$ sebagai subgraf dari $G$.

~\\ Dari \textbf{kasus 1} dan \textbf{kasus 2}, diperoleh $G_2 \supseteq W_n$. Oleh karena itu, haruslah $M_3(P_4,W_n) \leq \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil$.

~\\ Dengan demikian, disimpulkan $M_3(P_4,W_n) = \Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil$ untuk $n \geq 11$.
\end{proof}

\section{Kesimpulan}
Pada artikel ini diperoleh bilangan R-M-H $M_3(P_4,W_n)$ dengan hasil sebagai berikut.

$M_3(P_4,W_n) = $
$\begin{cases}
	4 &; n \in \{4,6\}
	\\
	5 &; n \in \{3,5,7,8,9,10\}
	\\
	\Bigl\lceil\dfrac{n+5}{3}\Bigr\rceil &; n \geq 11
\end{cases}$

\section{Ucapan Terima Kasih}
Penulis mengucapkan terima kasih kepada bapak Narwen, M.Si, ibu Radhiatul Husna, M.Si, dan bapak Dr. Admi Nazra yang telah memberikan kritikan dan saran sehingga artikel ini dapat diselesaikan dengan baik. 

\begin{thebibliography}{0}
\bibitem{Bondy} Bondy, J.A. dan Murty, U.S.R. 2008. \emph{Graph Theory, Graduate Texts in Mathematics}. Springer, New York

\bibitem{Burger1} Burger, A.P. dan Vuuren, J.H Van. 2004. Ramsey numbers in complete balance multipartite graphs, Part I: Set numbers. \emph{Discrete Mathematics}. \textbf{283}: 37-43

\bibitem{Burger2} Burger, A.P. dan Vuuren, J.H Van. 2004. Ramsey numbers in complete balance multipartite graphs, Part II: Size numbers. \emph{Discrete Mathematics}. \textbf{283}: 45-49

\bibitem{Chartrand} Chartrand, G., Lesniak, L, dan Zhang, P. 2016. \emph{Graphs and Digraphs. Sixth Edition}. CRC Press, Boca Rotan

\bibitem{Clark} Clark, J. dan Holton, D.A. 1995. \emph{A First Look at Graph Theory}. Allied Publishers LTD, Singapura

\bibitem{Lubis} Lubis, A.A. 2021. Bilangan Ramsey Multipartit Himpunan untuk Kombinasi Graf Lintasan dengan Graf Roda $M_4(P_3,W_n)$ dengan $n \geq 3$. \textit{Skripsi S-1}, tidak diterbitkan. Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Andalas

\bibitem{Radziszowski} Radziszowski, S.P. 2021. Small Ramsey numbers. \emph{The Electonic Journal of Combinatorics}. \textbf{16}: 4

\bibitem{Ramsey} Ramsey, A.P. 1928. On a problem of formal logic. \emph{Proceedings Of The London Mathematical Society}. \textbf{30}: 264-286

\bibitem{Wallis} Wallis, W.D. 2007. \emph{A Beginner's Guide to Graph Theory. Second Edition}. Birkhauser, Carbondale

\bibitem{Yuri} Yuri, R. 2020. Bilangan Ramsey Multipartit Himpunan untuk Kombinasi Graf Lintasan dengan Roda. \textit{Tesis S-2}, tidak diterbitkan. Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Andalas

\end{thebibliography}
\end{document}