Claim Missing Document
Check
Articles

Found 1 Documents
Search
Journal : Science and Technology Indonesia

Some Properties of Generalized Token Graphs Muna, Naelufa Syifna Wifaqotul; Raventino; Utami, Rintang; Lia, Febby Desy; Huda, Muhammad Nurul; Susanti, Yeni
Science and Technology Indonesia Vol. 11 No. 2 (2026): April
Publisher : Research Center of Inorganic Materials and Coordination Complexes, FMIPA Universitas Sriwijaya

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.26554/sti.2026.11.2.643-651

Abstract

The generalized k-token graph GFk(G) is a graph with the k-subsets of V(G) as the vertices, and two different vertices are adjacent if and only if the symmetric difference contains at least one edge of G. This model extends the classical k-token graph by relaxing the adjacency condition, leading to increased edge density and altered topological properties. In this paper, we establish the fundamental properties of GFk(G), including its connectivity, duality, and monotonicity. We provide exact formulas for the vertex degrees and the total size of GF2(G), along with combinatorial bounds for k > 2. Furthermore, we characterize the girth and clique numbers, proving that GFk(G) is highly prone to containing triangles even when the base graph is triangle-free. We also explore the inheritance of Hamiltonicity and bipartiteness, demonstrating that while connectivity is preserved, bipartiteness is lost for almost all bipartite graphs with at least four vertices. Our results provide a comprehensive structural characterization of this generalization, bridging the gap between classical token graphs and broader set-theoretic graph constructions.
Co-Authors Abdussalam, Muhammad Izzudin Afrizal Eko Nugroho Agung Wijoyo Ajizah, Imroatul Akbar, Paisal Amalia, Salma Rizqi Amanulloh, Naeni Amrina Munjiyah Amsar A. Dulmanan Anggraeni, Revy Dwi Anwar, Nur Kahfi Mukhlisin Ayunisa, Qurota Chahyati, Siti Daud Rismana Dwi, Muhammad Risqy Dyoty Auliya Vilda Ghasya Esa Prakasa, Esa Fadilah, Nadiah Nurli Fariz Alnizar Fatkhu Yasikh Fatkhu Yasikh Febry, Karima Dina Fitriyah, Nina Sa'idah Fitriyanti, Intan Diana Herlambang, Unu Putra Hidayatullah, Muhammad Yusuf Ika Puspita Sari Islamiah, Arifa Juri Ardiantoro Karimah, Nasikhatul Kristiawan*, Nana Lestari, Veni Rizki Lia, Febby Desy Maulidia, Hanifa Melani, Marina Minan, Ahasanul Mufidah, Vika Nurul Muhtar Said, Muhtar Muna, Naelufa Syifna Wifaqotul Munadi, Windya Rizki Dwi Munjiyah, Amrina Mu’minatun, Afrida Nadhifatuz Zulfa, Nadhifatuz Nadiah Nurli Fadilah Nafiiyah, Nur Nasywa Cinta Az Zahrah Nisrina Gina Rahma Nugroho, Afrizal Eko Nur Kahfi Mukhlisin Anwar Nur Kholis Nurkholisah, Siti Pramono, Sausan Rona Rafidah Puput Wanarti Rusimamto Putra, Romi Iriandi Putri, Shalsabilla Aulia Qurota Ayunisa Rafi Sulthan Rizqullah Rafidah Pramono, Sausan Rona Rahma, Nisrina Gina Rahma, Salsabila Ramadhan, Putri Utami Ramadhina, Zahra Rauhulloh Ayatulloh Khomeini Noor Bintang Raventino Retno Wardhani Rizqullah, Rafi Sulthan Robi’ah Machtumah Malayati Rosyidah, Titin Safara, Usfi Dwi Safira Ila Mardhatillah Samsuri, Muhammad Sanjaya, Ilyas Setyan, Ardath Prahara Shalsabilla Aulia Putri Shofiana, Khuly Siti Halidjah Solihan Solihan, Solihan Sulistyawaty, Ety Diana Sutikno, Putri Yanuarita Syahra, Inayatul Laely Unu putra Herlambang Utami, Rintang Vika Vika Nurul Mufidah Yasik, Fatkhu Yeni Susanti Zain, Muh Hamdi Zainal Arifin Zuhrie, Muhamad Syariffuddien ‘Ainiyyah, Cita Eka