Chulalongkorn University Theses and Dissertations (Chula ETD)

Other Title (Parallel Title in Other Language of ETD)


Year (A.D.)


Document Type


First Advisor

Chariya Uiyyasathian

Second Advisor

Nataphan Kitisin


Faculty of Science (คณะวิทยาศาสตร์)

Department (if any)

Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)

Degree Name

Master of Science

Degree Level

Master's Degree

Degree Discipline





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

Included in

Mathematics Commons



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.