Decomposition of complete multipartite graphs into disjoint unions of cycles - Uthoomporn Jongthawonwuth (Chulalongkorn University, 2013)
ให้ 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