Chulalongkorn University Theses and Dissertations (Chula ETD)

การแยกส่วนและการแยกส่วนประกอบที่เกี่ยวข้องกับกราฟลูกบาศก์กราฟ k-ส่วนบริบูรณ์ และกราฟต้นไม้

Other Title (Parallel Title in Other Language of ETD)

Decompositions and factorizations involving cubes, complete k-partite graphs and trees

Year (A.D.)

2001

Document Type

Thesis

First Advisor

วนิดา เหมะกุล

Faculty/College

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

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

คณิตศาสตร์

DOI

10.58837/CHULA.THE.2001.875

Abstract

วิทยานิพนธ์นี้ได้ศึกษาและรวบรวมผลงานที่เกี่ยวข้องกับการแยกส่วนและการแยกส่วนประกอบของกราฟลูกบาศก์ กราฟ k-ส่วนบริบูรณ์ และกราฟต้นไม้ กล่าวคือ การแยกส่วนของกราฟ n-ลูกบาศก์ Qn เป็นกราฟต้นไม้ n ด้าน ที่ถอดแบบกัน การแยกส่วนของกราฟสองส่วนบริบูรณ์ Kt, t เป็นกราฟ d-ลูกบาศก์ ที่ถอดแบบกัน เมื่อ t = 2(d-1) และการแยกส่วนประกอบของกราฟสองส่วนบริบูรณ์ Km, n เป็นกราฟต้นไม้ที่แผ่ไปทั่วที่ถอดแบบกัน นอกจากนี้เราแสดงการแยกส่วนของกราฟ k-ส่วน n-ลูกบาศก์ Q(k)(n) เป็นกราฟต้นไม้ n ด้าน ที่ถอดแบบกัน การแยกส่วนประกอบของกราฟ 3-ส่วนบริบูรณ์ K1, m, m(m-1) เป็นกราฟต้นไม้ที่แผ่ไปทั่วที่ถอดแบบกัน และไม่มีการแยกส่วนประกอบของกราฟ p-ส่วนบริบูรณ์ Km, m, ..., m เป็นกราฟต้นไม้ที่แผ่ไปทั่ว เมื่อ m, p>=2

Other Abstract (Other language abstract of ETD)

This thesis surveys and collects many classes of decompositions and factorizations involving cubes, complete k-partite graphs and trees, that is a decomposition of the n-cube Qn into isomorphic trees having n edges, a decomposition of the complete bipartite graph Kt, t into isomorphic d-cubes where t = 2(d-1) and a factorization of the complete bipartite graph Km,n into isomorphic spanning trees. Moreover, we show a decomposition of the graph k-ary n-cube Q(k)(n) into isomorphic trees having n edges, a factorization of the complete 3-partite graph K1, m, m(m-1) into isomorphic spanning trees and the complete p-partite graph Km, m,..., m can not be factorizable into spanning trees where m, p>=2.

Link to Full Text

Share

COinS