English  |  正體中文  |  简体中文  |  Items with full text/Total items : 49287/83828 (59%)
Visitors : 7150057      Online Users : 51
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    Please use this identifier to cite or link to this item: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/87477


    Title: Cyclically constructed 2k-sun graph designs
    Other Titles: 循環建構的2k-太陽圖設計
    Authors: 宋曉明;Sung, Hsiao-Ming
    Contributors: 淡江大學數學學系博士班
    高金美;Fu, Chin-Mei
    Keywords: 圖形分割;k-太陽圖;k-太陽圖系統;循環;1-旋轉;完全圖;完全均分圖;graph decomposition;k-sun graph;k-sun system;cyclic;1-rotational;complete graph;complete equipartite graph
    Date: 2012
    Issue Date: 2013-04-13 11:12:18 (UTC+8)
    Abstract: <pre>
    一個含有 v 個點的完全圖 Kv是指含有 v 個點且任二點都有邊相連的圖,又
    稱為 v 階完全圖。 一個圖頂點集合為 V 可以分成兩個互斥的集合 V1 與
    V2,且 V1中的每一點都與 V2中的每一點有邊相連,則稱此圖為一個完全二
    分圖。一個圖的頂點集合 V 可以分成 m 個兩兩互斥的集合 V1,V2,··· ,Vm,
    當 i neq j 時, Vi 中的每一點都與 Vj 中的每一點有邊相連,則稱此圖為完全
    m 分圖。 當 V1,V2,··· ,Vm 中元素的個數都為 n 時,則稱此圖為完全均分圖
    Km(n)。 一個 k-太陽圖 S(Ck) 是將一個 k-迴圈上的每一點分別向外連接一個
    懸掛邊,即另一端點度數為 1 的點,所成的圖。

    一個圖 G 的分割是圖 G 的子圖 H1,H2,··· ,Ht 所成的集合 H,其中
    E(H1)∪E(H2)∪···∪E(Ht) = E(G) 且 對於所有 i 6= j,E(Hi)∩E(Hj) =
    emptyset。若對於每一個 i = 1,2,··· ,t, Hi皆同構於 H,則我們說 G 有一個
    H-分割。一個 v 階的 k-太陽圖系統是指由 v 階的完全圖 Kv分割成 k-太陽圖後,
    這些 k- 太陽圖所成的集合。 存在 v 階 k-太陽圖系統的 v 所成的集合,稱為
    k-太陽圖系統的譜 Spec(k) 。

    本論文主要包括二個部份,一個是在完全圖中建構 k-太陽圖系統, 另一個
    是證明在完全均分圖中有 k-太陽圖-分割。

    在第三章中,當k = 6,10,14,2t(t geq 2)時,我們得到了k-太陽圖系統的譜
    如下:
    (1) Spec(2t) = {v|v ≡ 0,1 (mod 2t+2)} 其中 t geq 2.
    (2) Spec(6) = {v|v ≡ 0,1,9,16 (mod 24)}.
    (3) Spec(10) = {v|v ≡ 0,1,16,25 (mod 40)}.
    (4) Spec(14) = {v|v ≡ 0,1,8,49 (mod 56)}.
    並且對於階數大於 4k 時,我們建構出奇數階的循環 k-太陽圖系統與偶數階
    的1-旋轉 k-太陽圖系統。

    在第四章中,我們將焦點放在完全均分圖是否有 k-太陽圖-分割。當 k
    為偶數且 n ≡ 0 (mod 2k) 時,我們證明一個完全二分圖 Kn,n 有 2k-太陽
    圖-分割;而當(m,n) 滿足 mn geq 8 且 m(m - 1)n^2≡ 0 (mod 16)時, 除了
    (m,n) = (4,2) 之外,我們則證明了完全均分圖 Km(n)有 4-太陽圖-分割。
    </pre>
    <pre>
    A complete graph with v vertices, denoted by Kv, is a simple graph whose
    vertices are mutually adjacent. A complete bipartite graph is a graph G =
    (V,E) where V can be divided into two disjoint sets V1 and V2 and E
    contains all edges connecting every vertex in V1with all vertices in V2.
    If |V1| = m and |V2| = n, then G can be denoted as Km,n. A complete
    m-partite graph G = (V,E) is a graph such that the vertex set V can be
    partitioned into m parts, V1,V2,··· ,Vm, and E contains all edges which
    connect all vertices belong to different parts. If |Vi| = nifor each i =
    1,2,··· ,m, then G can be denoted as Kn1,n2,···,nm. If n1= n2= ··· = nm=
    n, this graph is called a complete equipartite graph with m parts of size
    n, and denoted by Km(n). A k-sun graph S(Ck) is obtained from the cycle
    of length k, Ck, by adding a pendant edge to each vertex of Ck.

    A decomposition of a graph G is a collection H = {H1,H2,··· ,Ht} of
    subgraphs of G such that E(H1) ∪ E(H2) ∪ ··· ∪ E(Ht) = E(G) and
    E(Hi)∩E(Hj) = emptyset for each i neq j. If Hi is isomorphic to a subgraph
    H of G for each i = 1,2,··· ,t, then we say that G has an H-decomposition.
    A k-sun system of order v is a decomposition of the complete graph Kv into
    k-sun graphs. The set of values of v for which there exists a k-sun system
    of order v is called the spectrum of a k-sun system, denoted by Spec(k).
    This dissertation includes two parts. One is about constructing a k-sun
    system of order v and another is about proving that complete equipartite
    graphs have k-sun decompositions.

    In chapter 3, when k = 6,10,14, and 2tfor t geq 2, we obtain the spectrum
    of k-sun systems as follows.
    (1) Spec(2t) = {v|v ≡ 0,1 (mod 2t+2)} for t geq 2,
    (2) Spec(6) = {v|v ≡ 0,1,9,16 (mod 24)},
    (3) Spec(10) = {v|v ≡ 0,1,16,25 (mod 40)}, and
    (4) Spec(14) = {v|v ≡ 0,1,8,49 (mod 56)}.
    We give the construction of cyclic k-sun system of odd order and
    1-rotational k-sun system of even order when the order is greater than 4k.

    In chapter 4, we give the construction of 2k-sun decomposition of Kn,nas k
    is even and n ≡ 0 (mod 2k) and construct 4-sun decomposition of Km(n)for
    mn geq 8 and m(m - 1)n^2≡ 0 (mod 16) except (m,n) = (4,2).
    </pre>
    Appears in Collections:[數學學系暨研究所] 學位論文

    Files in This Item:

    File SizeFormat
    index.html0KbHTML126View/Open

    All items in 機構典藏 are protected by copyright, with all rights reserved.


    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - Feedback