Please use this identifier to cite or link to this item:
Title: Decomposition of complete multipartite graphs into disjoint unions of cycles
Other Titles: การแยกกราฟหลายส่วนบริบูรณ์ออกเป็นยูเนียนของวัฎจักรที่ไม่มีส่วนร่วมกัน
Authors: Uthoomporn Jongthawonwuth
Advisors: Chariya Uiyyasathian
Saad I.El-Zanati
Other author: Chulalongkorn University. Faculty of Science
Advisor's Email:
No information provided
Subjects: G-Design
Steiner tripple system
The Bose Construction
The Oberwolfach Problem
Graph theory
Perfect graphs
Issue Date: 2013
Publisher: Chulalongkorn University
Abstract: Let G be a 2-regular graph of odd order n and let v be a positive integer. It is of interest to know when there exists a G-decomposition of Kv. If v ≡ 1 or n (mod 2n), then v satis es the necessary conditions for the existence of a Gdecomposition of Kv. If G contains exactly one odd cycle, it is known that there exists a G-decomposition of Kv for all v ≡ 1 (mod 2n). In this dissertation, we focus on G-decompositions of complete multipartite graphs. For positive integers r and s, let Kr×s denote the complete multipartite graph with r parts of order s each. We use a novel extension of the Bose construction for Steiner triple systems to show that there exists a G-decomposition of K(2k+1)×n for every positive integer k and a G-decomposition of Kk′×2n for every integer k′ ≥ 3. Furthermore, if G has only two components, we nd G-decompositions of Kv for all v ≡ n (mod 2n) unless G = C4 ∪ C5 and v = 9. Additionally, if G consists of three odd cycles, we nd G-decompositions of K(2k+1)×n for every positive integer k, of Kk′×2n for every integer k′ ≥ 3, and of Kv for all v ≡ 1 (mod 2n), except v = 4n + 1.
Other Abstract: ให้ G เป็นกราฟที่มี n จุด โดยที่ n เป็นจำนวนคี่ แต่ละจุดมีดีกรี 2 และให้ v เป็นจำนวนเต็มบวก คำถามที่น่าสนใจคือเมื่อไหร่จะสามารถแยกกราฟบริบูรณ์ Kᵥ ออกเป็นกราฟ G ได้ ถ้า v หรือ n(mod2n) แล้ว v จะสอดคล้องกับเงื่อนไขจำเป็นของการแยกกราฟบริบูรณ์ Kᵥ ออกเป็นกราฟ Gได้ ถ้ากราฟ G มีกราฟย่อยที่เป็นวัฏจักรที่มีจำนวนจุดเป็นคี่เพียงวงเดียวเท่านั้น แล้วเป็นที่ทราบว่าจะสามารถแยกกราฟบริบูรณ์ Kᵥ ออกเป็นกราฟ G ได้ สำหรับทุก v 1n(mod2n) ในวิทยานิพนธ์ฉบับนี้ เราเน้นการศึกษาการแยกกราฟหลายส่วนบริบูรณ์ออกเป็นกราฟ G สำหรับจำนวนเต็มบวก r และ s ให้ Kᵣₓs แทนกราฟหลายส่วนบริบูรณ์ที่มี r ส่วนแต่ละส่วนมีจำนวนจุดเป็น s เราได้ขยายวิธีการสร้างระบบสามเหลี่ยมสไตน์เนอร์ของโบสเพื่อแสดงการมีอยู่ของการแยกกราฟหลายส่วนบริบูรณ์ K(2k+1)xn ออกเป็นกราฟ G สำหรับทุกจำนวนเต็มบวก K และการมีอยู่ของการแยกกราฟหลายส่วนบริบูรณ์ Kkx2n ออกเป็นกราฟ G สำหรับทุกจำนวนเต็ม k≥3 นอกจากนี้ถ้า G ประกอบด้วยกราฟวัฏจักรสองวง แล้วเราสามารถแยกกราฟบริบูรณ์ Kᵥ ออกเป็นกราฟ G สำหรับทุก v n(mod2n) เว้นแต่ G = C₄ EC₅ และ v = 9 ยิ่งไปกว่านั้น ถ้า G ประกอบจากวัฏจักรสามวงที่แต่ละวงมีจำนวนจุดเป็นคี่ แล้วเรายังพบว่าสามารถแยกกราฟหลายส่วนบริบูรณ์ K(2k+1)xn สำหรับทุกจำนวนเต็มบวก k และ Kkx2n สำหรับทุกจำนวนเต็ม k≥3 ออกเป็นกราฟ G ได้ และสามารถแยกกราฟบริบูรณ์ Kᵥ ออกเป็นกราฟ G ได้ สำหรับทุก v1(mod2n) เว้นแต่ v=4n+1
Description: Thesis (Ph.D.)--Chulalongkorn University, 2013
Degree Name: Doctor of Philosophy
Degree Level: Doctoral Degree
Degree Discipline: Mathematics
Type: Thesis
Appears in Collections:Sci - Theses

Files in This Item:
File Description SizeFormat 
uthoomporn_jo.pdf1.2 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.