|
Decomposition of complete multipartite graphs into disjoint unions of cycles |
|---|---|
| รหัสดีโอไอ | |
| Title | Decomposition of complete multipartite graphs into disjoint unions of cycles |
| Creator | Uthoomporn Jongthawonwuth |
| Contributor | Chariya Uiyyasathian, Saad I.El-Zanati |
| Publisher | Chulalongkorn University |
| Publication Year | 2556 |
| Keyword | G-Design, G-Decomposition, Steiner tripple system, The Bose Construction, The Oberwolfach Problem, Graph theory, 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. |
| URL Website | cuir.car.chula.ac.th |
