English  |  正體中文  |  简体中文  |  Items with full text/Total items : 55023/89277 (62%)
Visitors : 10604314      Online Users : 27
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/94023

    Title: Packing graphs with 4-cycles
    Other Titles: 4-迴圈裝填圖的探討
    Authors: 徐育鋒;Hsu, Yu-Fong
    Contributors: 淡江大學數學學系博士班
    高金美;Kau Fu, Chin-Mei
    Keywords: 完全圖;裝填;4-迴圈系統;4-正則圖;complete graph;packing;4-cycle system;4-regular graph
    Date: 2013
    Issue Date: 2014-01-23 13:48:17 (UTC+8)
    Abstract: 一個n個點的完全圖是一個任兩點皆相鄰的簡單圖,記作Kn。一個n個點的迴圈稱為n-迴圈且記作(v1, v2, …, vn),其中v1, v2, …, vn為迴圈的點且v1v2, v2v3, …, vn−1vn, vnv1為迴圈的邊。一個4-正則圖是一個每一點度數皆為4的圖。假如G是Kn的子圖,則Kn –E(G)是一個將Kn中所有圖G的邊皆移除的圖。假如C是圖Q的一個k-迴圈系統,則C是一個蒐集Q中邊互斥的k-迴圈之集合且Q中的每一邊只會出現在C中唯一的一個k-迴圈中,也就是說,Q 可以被分割成k-迴圈。在本篇論文中,我們得到下列結果:

    (1) 幾乎所有點數至少為8的4-正則圖皆為3-可縮減。
    (2) 令G是一個t個點的4-正則圖。
    (i) 假如G是一個由t個點互斥的K5所組成且G是(n,5t)-可容
    許,則當n ≡ 1,5 (mod 8)時,Kn – E(G)存在一個4-迴
    (ii) 假如G是(n,t)-可容許且n ≥ (4t – 5)/3,則當n ≡ 1,
    5 (mod 8)時,Kn – E(G)存在一個4-迴圈系統,除了K9 – E(G), 其中G跟兩個點數為8的4-正則圖同構。

    A complete graph with n vertices is a simple graph whose vertices are pairwise adjacent, denoted by Kn. A cycle with n vertices is called an n-cycle and is denoted (v1, v2, …, vn), where v1, v2, …, vn are the vertices of the cycle and v1v2, v2v3, …, vn−1vn, vnv1 are the edges. A 4-regular graph is a graph whose degree of each vertex is 4. If G is a subgraph of Kn, then Kn –E(G) is the graph by removing all edges of G from Kn. If C is a k-cycle system of a graph Q, then C is the set of edge-disjoint k-cycles in Q and each edge of Q occurs in exactly one of k-cycles in C, i.e., Q can be decomposed into k-cycles. In this thesis, we obtain the following results:

    (1) Almost all 4-regular graphs of order at least 8 are
    (2) Let G be a 4-regular graph of order t.
    (i) If G is a vertex-disjoint union of t copies of K5
    and G is (n,5t)-admissible, then there exists a
    4-cycle system of Kn – E(G) for n ≡ 1, 5
    (mod 8).
    (ii) If G is (n,t)-admissible and n ≥ (4t − 5)/3, then
    there exists a 4-cycle system of Kn – E(G), for
    n ≡ 1, 5 (mod 8), except that K9 – E(G), where G
    is isomorphic to two 4-regular graphs of order 8.
    Appears in Collections:[Graduate Institute & Department of Mathematics] Thesis

    Files in This Item:

    File SizeFormat

    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