Decomposition of complete multipartite graphs into disjoint unions of cycles

การแยกกราฟหลายส่วนบริบูรณ์ออกเป็นยูเนียนของวัฎจักรที่ไม่มีส่วนร่วมกัน

Name: Uthoomporn Jongthawonwuth

ThaSH: G-Design

ThaSH: G-Decomposition

ThaSH: Steiner tripple system

ThaSH: The Bose Construction

ThaSH: The Oberwolfach Problem

ThaSH: Graph theory

ThaSH: Perfect graphs

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.

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

Chulalongkorn University. Office of Academic Resources

Address: BANGKOK

Email: cuir@car.chula.ac.th

Name: Saad I.El-Zanati

Role: Advisor

Name: Chariya Uiyyasathian

Role: Advisor

Created: 2013

Modified: 2020-06-23

Issued: 2020-06-23

วิทยานิพนธ์/Thesis

application/pdf

URL: http://cuir.car.chula.ac.th/handle/123456789/51794

eng

DegreeName: Doctor of Philosophy

Level: Doctoral Degree

Descipline: Mathematics

Grantor: Chulalongkorn University

©copyrights Chulalongkorn University

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	uthoomporn_jo.pdf	1.17 MB

ใช้เวลา

0.024068 วินาที