SIFAT-SIFAT GRAF JUMLAHAN M-BONACCI

MARIA WINDA EKA P, Dr. Drs. Budi Surodjo, M.Si.

2023 | Skripsi | S1 MATEMATIKA

Untuk setiap $n$ dan $m$ bilangan bulat positif, graf jumlahan $m$-\emph{bonacci} yang dilambangkan dengan $G_{m,n}$ didefinisikan sebagai graf dengan simpul 1, 2, ..., $n$ dan dua simpul dalam graf $G_{m,n}$ \emph{adjacent} jika dan hanya jika jumlahan kedua simpul tersebut merupakan bilangan $m$-\emph{bonacci}. \emph{Path Hamilton} didefinisikan sebagai \emph{path} yang melalui semua simpul dalam suatu graf. Pada skripsi ini dibahas mengenai nilai $m$ dan $n$ sedemikian hingga komponen graf $G_{m,n}$ memiliki \emph{path Hamilton}. Ada beberapa sifat dari graf jumlahan $m$-\emph{bonacci} yang harus dicari sebelum mencari keberadaan \emph{path Hamilton}, seperti derajat simpul, keberadaan simpul terisolasi, komponen graf, dan sikel. Hasil dari skripsi ini yaitu setiap komponen graf $G_{1,n}$ memiliki \emph{path Hamilton}, setiap komponen graf $G_{2,n}$ memiliki \emph{path Hamilton} ketika $n \in \{9,11,Z_{k,m},Z_{k+1,m}\}$, setiap komponen graf $G_{3,n}$ memiliki \emph{path Hamilton} ketika $n \le 9$, setiap komponen graf $G_{4,n}$ memiliki \emph{path Hamilton} ketika $n \le 11$, dan setiap komponen graf $G_{m,n}$ dengan $m \ge 5$ memiliki \emph{path Hamilton} ketika $n \le 12$.

For each positive integers $n$ and $m$, the $m$-\emph{bonacci}-sum graph, denoted by $G_{m,n}$ is defined as a graph with vertices $1,2,3,...,n$ and two vertices are adjacent if only if the sum of the two vertices is a $m$-\emph{bonacci} number. A \emph{Hamilton} path is defined as a path that traverses all vertices of a graph. This research discusses the values of $m$ and $n$ so that the component of a graph $G_{m,n}$ has a \emph{Hamilton} path. There are several properties of the $m$-\emph{bonacci}-sum graph that must be looked for before looking for the existence of a \emph{Hamilton} path, such as the degree of vertices, isolated vertices, components, and cycles. According to the research findings, each component of a graph $G_{1,n}$ has a \emph{Hamilton} path, each component of a graph $G_{2,n}$ has a \emph{Hamilton} path when $n \in \{9, 11, Z_{k,m}, Z_{k,m}-1\}$, each component of a graph $G_{3,n}$ has a \emph{Hamilton} path when $n \le 9$, each component of a graph $G_{4,n}$ has a \emph{Hamilton path} when $n \le 11$, each component of a graph $G_{m,n}$ with $m \ge 5$ has a \emph{Hamilton} path when $n \le 12$.

Kata Kunci : graf, $m$-\emph{bonacci}, \emph{path Hamilton}