English  |  正體中文  |  简体中文  |  Items with full text/Total items : 51897/87065 (60%)
Visitors : 8467950      Online Users : 202
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/102163


    Title: 完全二部圖中C4與C6飽和子圖的探討
    Other Titles: The study of C4,C6-saturated bipartite graphs
    Authors: 張博淳;Chang, Po-Chun
    Contributors: 淡江大學數學學系碩士班
    高金美;Kau, Chin-Mei
    Keywords: Zarankiewicz問題;二部圖;C4與C6飽和圖;Zarankiewicz problem;bipartite graph;C4, C6-saturated graph
    Date: 2014
    Issue Date: 2015-05-04 09:48:57 (UTC+8)
    Abstract: 一個C4與C6飽和二部圖是一個不含有C4與C6的二部圖,且加上任意不相鄰兩點的邊後會形成C4或C6。我們要探討的是一個C4與C6飽和二部圖的邊數為多少。在本論文中,我們令z(m, n)為二部圖Km,n的子圖中為C4與C6飽和圖的最多邊數,s(m, n)為最少邊數。我們獲得以下的結果:
    1.s(m ,n)=m+n-1
    2.∀n≥3,z(3, n)=n+2、∀n≥4,z(4, n)=n+4,∀n≥6,z(5, n)=n+6
    3.若n≥⌊m^2/4⌋,則z(m,n)= ⌊m^2/4⌋+n
    4.設 n≥⌊m^2/4⌋,若s(m ,n)≤ x ≤z(m ,n),則在 K_(m,n) 中存在一個
    C4與C6飽和圖其邊數為x。
    A C4, C6-saturated bipartite graph is a bipartite graph if it contains no 4-cycle and 6-cycle, but joining any nonadjacent vertices produces a graph that does contain a 4-cycle or 6-cycle. We will find the number of edges of a C4, C6-saturated bipartite graph. We let z(m, n) be the maximum number of edges of a C4,C6-saturated bipartite graph in Km,n, and s(m, n) be the minimum number of edges of a C4, C6-saturated bipartite graph in Km,n.
    In this thesis, we obtains the following results:

    1.s(m,n)=m+n-1
    2.∀n ≥ 3, z(3, n) = n+2, ∀n≥4, z(4, n) = n+4, ∀n≥6, z(5, n)= n+6.
    3.If n≥⌊m^2/4⌋,then z(m,n)= ⌊m^2/4⌋+n
    4.Let n≥⌊m^2/4⌋. If s(m,n)≤ x ≤z(m,n), then there exists a subgraph
    of K_(m,n) which is a C4, C6-saturated graph, and the number of edges is x.
    Appears in Collections:[數學學系暨研究所] 學位論文

    Files in This Item:

    File SizeFormat
    index.html0KbHTML65View/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