English  |  正體中文  |  简体中文  |  Items with full text/Total items : 49287/83828 (59%)
Visitors : 7157382      Online Users : 83
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/87462


    Title: 不含 K2,2 的二分極圖
    Other Titles: Extremal K2,2-free bipartite graphs
    Authors: 賴尚欣;Lai, Shang-Hsin
    Contributors: 淡江大學中等學校教師在職進修數學教學碩士學位班
    高金美;Fu, Chin-Mei Kau
    Keywords: Zarankiewicz問題;極圖;二分圖;導出子圖;圖的分割;Zarankiewicz problem;extremal graph;bipartite graph;graph decomposition
    Date: 2012
    Issue Date: 2013-04-13 11:09:42 (UTC+8)
    Abstract: 一個不含 K_2,2 的二分極圖是一個含有最多邊數且不含有子圖 K_2,2 的二分圖。若此二分圖為 K_m,n 的子圖,則求此二分極圖的邊數的問題也就是出名的Zarankiewicz 問題。在本論文中,我們令f(m,n)為 K_m,n 中不含 K_2,2 的二分極圖的邊數。我們獲得以下的結果:
    ①f(m,n)≤n/2+√(mn(m-1)+n^2/4)
    ②若 n≥(m|2),則 f(m,n)=(m|2)+n。
    ③若 m≡1,3 (mod 6),則 K_m 恰可分割成 m(m-1)/6 個邊相異的 K_3 子圖,且f(m,n)=(m|2)。
    ④若 ((m|2))/3≤n≤(m|2),則 f(m,n)=[((m|2)+3n)/2] 。
    ⑤若 m≡1,4 (mod 12),則 K_m 恰可分割成 m(m-1)/12 個邊相異的 K_4 子圖,且,f(m,n)=2(m|2)/3。
    An extremal K_2,2-free bipartite graphs is a bipartite graph which contains the maximum number of edges and does not contain any subgraph K_2,2. If this bipartite graph is a subgraph of K_m,n, then finding the number of edges of the extremal bipartite graph is the well-known Zarankiewicz Problem. In this thesis, we let f(m,n) be the number of edges of the extremal K_2,2-free bipartite graph which is a subgraph of K_m,n. We obtain the following results:
    ①f(m,n)≤n/2+√(mn(m-1)+n^2/4)
    ②If ≥(m|2), then f(m,n)=(m|2)+n.
    ③If m≡1,3 (mod 6), then K_m decompose into (m(m-1))/6 edge-disjoint K_3 subgraphs, and f(m,n)=(m|2).
    ④If ((m|2))/3≤n≤(m|2), then f(m,n)=[((m|2)+3n)/2] .
    ⑤If m≡1,4 (mod 12), then K_m decompose into (m(m-1))/12 edge-disjoint K_4 subgraphs, and f(m,n)=2(m|2)/3.
    Appears in Collections:[數學學系暨研究所] 學位論文

    Files in This Item:

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