SEPUTAR GRAF 2-TOKEN ATAS BEBERAPA GRAF DI DALAM KELUARGA GRAF KECEBONG

Ramadhani Latief Firmansyah, Prof. Dr.rer.nat. Yeni Susanti, S.Si., M.Si.

2025 | Skripsi | MATEMATIKA

Diberikan sebarang graf sederhana dan tidak berarah G = (V(G), E(G)) dan bilangan bulat positif k. Graf 2-token atas graf G adalah suatu graf dengan himpunan simpulnya adalah semua himpunan bagian sejati dari himpunan simpul V(G) dari graf G dengan banyak anggotanya adalah sebanyak dua dan dua simpul berbeda di dalam graf tersebut bertetangga jika dan hanya jika selisih simetri dari kedua simpul tersebut merupakan sebuah rusuk di dalam graf G. Pada skripsi ini akan dibahas beberapa graf di dalam keluarga graf kecebong yaitu graf kecebong T_{m, n}, graf kacamata simetris SG_{m, n}, graf borgol simetris SHC_m, graf wajan P_{m, 1}, dan graf badan B_{m, 2} yang meliputi definisi, contoh, dan beberapa sifat graf-graf tersebut. Lebih lanjut, pada skripsi ini akan dibahas juga graf 2-token atas graf-graf tersebut yang meliputi contoh, isomorfisme, sifat keplanaran, sifat ke-Eulerian, sifat ke-Hamiltonian, bilangan kromatik, diameter, dan bilangan girth dari graf-graf 2-token tersebut.

Given any simple and undirected graph G = (V(G), E(G)) and a positive integer k. The 2-token graph of graph G is a graph whose vertex sets are all proper subsets of the vertex set V(G) of the graph G with the number of elements is 2 and two distinct vertices in the graph are adjacent if and only if the symmetric difference of the two vertices is an edge in the graph G. In this thesis, several graphs in the tadpole graph family will be discussed, namely the tadpole graph T_{m, n}, the symmetric glasses graph SG_{m, n}, the symmetric handcuff graph SHC_m, the pan graph P_{m, 1}, and the body graph B_{m, 2}, including definitions, examples, and several properties of these graphs. Furthermore, this thesis also discusses 2-token graphs of these graphs, including examples, isomorphisms, planarity properties, Eulerian properties, Hamiltonian properties, chromatic numbers, diameters, and girth numbers of these 2-token graphs.

Kata Kunci : graf k-token, graf 2-token, graf kecebong, graf kacamata simetris, graf borgol simetris, graf wajan, graf badan