Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
การแยกคลีกวัฏจักรของกำลังของวง
Year (A.D.)
2018
Document Type
Thesis
First Advisor
Chariya Uiyyasathian
Second Advisor
Nataphan Kitisin
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Mathematics
DOI
10.58837/CHULA.THE.2018.327
Abstract
A clique decomposition P of a graph G is a collection of cliques of G such that each edge of G belongs to exactly one clique in the collection. We say that P is cyclic if there is an isomorphism : V (G)→ V (G) such that Kk{α (v₁), α (v₂), α (v₃), ... , α (vk)g is a clique in P whenever Kk{v₁; v₂; v₃; :::; vk} is. The k-power of an n-cycle, Ck n, is the graph having the same vertex set as Cn and uv is an edge in Ck n if and only if dCn(u; v) ≤ k. Partly inspired by the solution of Heffter's difference problem, we introduce a certain construction of cyclic clique decompositions of the k-power of an n-cycle. Finally, we establish an optimal cyclic clique decomposition into cliques of order at most 4 for each 3 ≤ k ≤ 26 and all natural numbers n > 3k.
Other Abstract (Other language abstract of ETD)
การแยกคลีก P ของกราฟ G คือ หมู่ของคลีกของกราฟ G ซึ่งทำให้เส้นเชื่อมแต่ละเส้น บนกราฟ G ปรากฏอยู่บนคลีกเดียวเท่านั้นในหมู่ดังกล่าว โดยเราจะกล่าวว่า P เป็น วัฏจักร ถ้ามีฟังก์ชันสมสัณฐาน α : V (G) → V (G) ที่ทำให้Kk{ α (v₁); (v₂); (v₃); :::; (vk)g เป็นคลีกใน P ก็ต่อเมื่อ Kk{fv₁; v₂; v₃; :::; vkg เป็นคลีกใน P และ กำลังที่ k ของวงขนาด n เขียนแทนด้วยสัญลักษณ์Ck n คือกราฟที่มีเซตของจุดยอดเท่ากับเซตของจุดยอดของกราฟ Cn โดย uv เป็นเส้นเชื่อมของกราฟ Ck n ก็ต่อเมื่อ dCn(u, v) ≤ k เราจะแนะนำการสร้างการแยกคลีก วัฏจักรของกำลังที่k ของวง n จุดซึ่งได้รับแรงบันดาลใจจากผลเฉลยของข้อปัญหาผลต่างของเฮฟ เตอร์สุดท้ายนี้เราได้สร้างการแยกคลีกวัฏจักรของกำลังของวงออกเป็นคลีกอันดับไม่เกินสี่แบบ เหมาะที่สุด สำหรับ 3 ≤ k ≤ 26 และทุกจำนวนนับ n > 3k
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Peereeyaphat, Apiwat, "Cyclic clique decompositions of powerof cycles" (2018). Chulalongkorn University Theses and Dissertations (Chula ETD). 2458.
https://digital.car.chula.ac.th/chulaetd/2458