Chulalongkorn University Theses and Dissertations (Chula ETD)

Decomposition of complete multipartite graphs into disjoint unions of cycles

Other Title (Parallel Title in Other Language of ETD)

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

Year (A.D.)

2013

Document Type

Thesis

First Advisor

Chariya Uiyyasathian

Second Advisor

Saad I.El-Zanati

Faculty/College

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

Degree Name

Doctor of Philosophy

Degree Level

Doctoral Degree

Degree Discipline

Mathematics

DOI

10.58837/CHULA.THE.2013.874

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 (Other language abstract of ETD)

ให้ 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

Link to Full Text

Share

COinS