Beberapa Karakterisasi Graf Token-2 atas Graf Ranting Daun Tunggal

Muhammad Taqiyuddin Hidayatullah, Prof. Dr.rer.nat. Yeni Susanti, M.Si.

2026 | Skripsi | MATEMATIKA

Diberikan suatu graf sederhana dan tidak berarah G = (V(G), E(G)) serta suatu bilangan bulat positif k. Graf token-k atas graf G, dinotasikan dengan F_k(G), adalah graf dengan himpunan simpulnya beranggotakan semua subhimpunan dari V(G) yang memiliki anggotak sebanyak k elemen, dan dua simpul bertetangga jika dan hanya jika selisih simetri dari kedua subhimpunan tersebut merupakan sebuah sisi pada graf G.

Pada skripsi ini dibahas graf token-2 atas graf ranting daun tunggal P_n^k, yaitu graf yang  diperoleh dari graf lintasan P_n dengan menambahkan satu simpul daun yang terhubung pada simpul ke-k. Pembahasan difokuskan pada karakterisasi graf token-2 atas graf tersebut melalui konstruksi suatu graf yang dinotasikan dengan \phi_n^k.

Hasil utama dalam skripsi ini meliputi karakterisasi graf token-2 atas graf ranting daun tunggal, serta penentuan beberapa sifat graf yang terkait, antara lain orde, ukuran, diameter, dan radius graf. Selain itu, ditunjukkan pula bahwa graf token-2 atas graf ranting daun tunggal memiliki karakterisasi yang dapat dianalisis secara sistematis melalui graf yang dibentuk.

Let G = (V(G), E(G)) be a simple and undirected graph and let k be a positive integer. The k-token graph of G, denoted by F_k(G), is a graph whose vertex set consists of all k-subsets of V(G), where two vertices are adjacent if their symmetric difference is an edge of G.

In this undergraduate thesis, the 2-token graph of a single-leaf branched path graph P_n^k is studied. The graph P_n^k is obtained from the path graph P_n by attaching a single leaf vertex to the k-th vertex of the path. The discussion focuses on the characterization of the 2-token graph of P_n^k by constructing a comparison graph, denoted by \phi_n^k.

The main results of this thesis include the characterization of the 2-token graph of the single-leaf branched path graph and the determination of several graph properties, namely the order, size, diameter, and radius of the graph. Furthermore, it is shown that the characterization of the 2-token graph can be systematically analyzed through the constructed comparison graph.

Kata Kunci : graf token-2, graf lintasan, graf ranting daun tunggal, diameter, radius, sifat Euler, sifat Hamilton.