Cyclically Constructed p-sun Graph Designs
| Autor: | Yuan-Lung Lin, 林遠隆 |
|---|---|
| Rok vydání: | 2012 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 100 A complete multigraph of order n and index λ, denoted by λKn, is a graph with n vertices, where any two distinct vertices u and v are joined by λ edges uv. A decomposition of a graph G is a collection H = {H_1, H_2, ..., H_t} of subgraphs of G such that E(H_1)∪E(H_2)∪...∪E(H_t) = E(G) and E(H_i)∩E(H_j) = φ for i ≠ j. If H_i is isomorphic to a graph H for each i = 1, 2, ..., t, then we say that G has an H-decomposition. A k-sun graph S(C_k) is a graph obtained from a k-cycle by adding a pendent edge to each vertex of the k-cycle. Let G be a graph. A G-design of λK_v, denoted by (K_v, G, λ)-design, is a pair of (X, B) where X is the vertex set of K_v and B is a collection of subgraphs of K_v, called blocks, such that each block is isomorphic to G and any edge in K_v is in exactly λ blocks of B. If λ = 1, then we call it a (K_v, G)-design for short. A (K_v, S(C_k), λ)-design is a decomposition of the complete multigraph λKv into k-sun graphs. In Chapter 2, we obtain the necessary and sufficient conditions for the decomposition of complete tripartite graphs with at least two partite sets having the same size into 3-suns and give the constructions to decompose K_{p,p,r} into 3-suns. Moreover, we decompose K_{2n,2n,2n} into 3-suns cyclically, and embed a cyclic Steiner triple system of order n into a 3-sun system of order 2n － 1, for n ≡ 1 (mod 6). In Chapter 3, we use the result of decomposing Kp,p,r into 3-suns to construct a (K_v, S(C_3))-design recursively. In Section 3.2, we obtain the cyclic (K_v, S(C_3))-design for v ≡ 1(mod 12), the 1-rotational (K_v, S(C_3))-design for v ≡ 0, 4 (mod 12), and then cyclically construct (K_v, S(C_3))-design for v ≡ 9 (mod 12). Furthermore, in Section 3.3, we cyclically construct (K_v, S(C_3), λ)-design for all λ when λn(n － 1) ≡ 0 (mod 12). In Chapter 4, we consider the construction of (K_v, S(C_5))-designs. We obtain a cyclic 5-sun system of order v as v ≡ 1, 5 (mod 20) and a 1-rotational 5-sun system of order v as v ≡ 0 (mod 20). For v ≡ 16 (mod 20), we use recursive construction to get (K_v, S(C_5))-design. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|