Seputar Graf 2-Token atas Graf Sikel dan Graf Kelereng

Ardian Arif Widiansyah, Prof. Dr.rer.nat. Yeni Susanti, S.Si., M.Si.

2025 | Skripsi | MATEMATIKA

Diberikan graf sederhana dan tak berarah G = (V (G), E(G)) dengan order n serta bilangan bulat k dengan 1 ? k ? n ? 1. Graf token ?k(G) didefinisikan sebagai graf dengan himpunan titik berupa himpunan semua subset V (G) dengan k anggota serta untuk setiap dua titik akan bertetangga jika dan hanya jika selisih simetrisnya merupakan pasangan titik yang bertetangga di G. Pada skripsi ini akan dibahas sifat-sifat dari graf 2-token atas graf sikel C_n dan graf 2-token atas graf kelereng MR_n. Sifat-sifat tersebut meliputi order, ukuran, diameter, bilangan kromatik, bilangan girth, bilangan independence, sifat eulerian, sifat hamiltonian, sifat keplanaran serta isomorfisme.

Given an undirected and simple graph G = (V(G), E(G)) of order n, and integer k with 1 ? k ? n ? 1. The token graph ?k(G) is a graph with the set of all k-subsets of V (G) as the vertex set, and two vertices are adjacent in ?k(G) if and only if their symmetric difference is a pair of adjacent vertices in G. In this thesis, it is discussed the properties of 2-token graph of cycle graph C_n and 2-token graph of marble graph MR_n. The properties are including order, size, diameter, chromatic number, girth number, independence number, eulerian path, hamiltonian path, planarity, and isomorfism.

Kata Kunci : Graf Token, Graf k-Token, Graf 2-Token, Graf Sikel, Graf Kelereng, Graf Sikel Layer