English  |  正體中文  |  简体中文  |  Items with full text/Total items : 49645/84944 (58%)
Visitors : 7699767      Online Users : 84
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/32902


    Title: 完全雙分圖中不含C4飽和子圖的探討
    Other Titles: The study of C4-saturated bipartite graphs
    Authors: 林泰平;Lin, Tai-ping
    Contributors: 淡江大學數學學系碩士班
    高金美;Kau, Chin-mei
    Keywords: ;雙分圖;不含C4的飽和圖;graph;bipartite graph;C4-saturated
    Date: 2006
    Issue Date: 2010-01-11 02:57:02 (UTC+8)
    Abstract: 如果圖G中不含C4,但再增加一邊之後就會產生C4,則稱圖G是不含C4的飽和圖。圖G為在Km,n中不含C4的飽和子圖,即表示圖G為Km,n的子圖,且為不含C4的飽和圖。在此篇論文中,主要是討論在Km,n中不含C4飽和子圖的可能邊數。我們令S(m,n)={t︱存在G為在Km,n中不含C4的飽和子圖,且︱E(G)︱=t},利用組合設計中之史坦納三元系及Bryant和Fu論文中判別圖G是否為含有最多邊的不含C4的飽和圖的建構法,而獲得當n足夠大時S(m,n)的最大值,及m≡0,1,2,3(mod 6)時S(m,n)的最大值。當1≦m≦6時,獲得S(m,n)的所有元素,進而建構出一些在Km,n中不含C4的飽和子圖,產生S(m,n)中所含的一些元素。
    A C4-saturated graph is a graph G which contains no C4,but when adding any edge in G will results C4.A C4-saturated bipartite graph in Km,n is a subgraph G of Km,n and G is a C4-saturated graph.In this thesis,we consider the possible number of edges of C4-saturated bipartite graphs in Km,n .We define S(m,n)={t|there exists a graph G which is a C4-saturated bipartite graph in Km,n with t edges}.By using the Steiner triple system in combinatorial designs and the construction in the paper of Bryant and Fu which showed that a maximum C4-saturated bipartite graph in Km,n ,we obtain the maximum value of S(m,n) when n is large or m≡0,1,2,3(mod 6).After that,we obtain the spectrum of S(m,n) when 1≦m≦6.We get some elements in S(m,n).
    Appears in Collections:[數學學系暨研究所] 學位論文

    Files in This Item:

    File SizeFormat
    0KbUnknown179View/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