Graf k-Token atas Graf

MEI MEGA UTAMI, Dr.rer.nat. Yeni Susanti, S.Si., M.Si.

2022 | Skripsi | S1 MATEMATIKA

Diberikan graf tak berarah sederhana G dan bilangan bulat positif k. Graf k-token atas suatu graf G adalah graf dengan himpunan titiknya adalah semua himpunan bagian dengan kardinalitas k dari himpunan titik di graf G dan dua titik berbeda berikatan jika dan hanya jika selisih simetri dari kedua titik tersebut merupakan sebuah sisi di G. Pada skripsi ini dibahas sifat-sifat dasar graf k-token atas graf dan karakteristik graf k-token atas graf kipas dan graf roda. Selain itu, dibahas pula hubungan graf 2-token dengan jenis-jenis graf khusus meliputi graf komplit, graf chordal, graf bebas segitiga, graf pohon, graf bintang, graf bipartit, graf sikel, dan graf siklik.

Let G be a simple undirected graph and let k be a positive integer. The k-token graph of graph G is the graph which vertex set consists of all k-subsets of vertex set of G and two different vertices are adjacent if and only if their symmetric difference is an edge of G. Several basic results on k-token graphs of graph G and the characteristics of the k-token graphs of fan graphs and wheel graphs are presented in this thesis. Moreover, the connection between the 2-token graph and and other kind of graph, such as complete graph, chordal graph, triangle free graph, tree, star graph, bipartite graph, cycle graph, and cyclic graph are also discussed in this thesis.

Kata Kunci : Graf Token, Graf k-Token, Graf Johnson, Graf Hamiltonian