在此論文中,主要介紹圖中一定條件的不交團及獨立的圈在一些二分圖中的相關(guān)結(jié)果.本文令G代表一個圖,它的頂點集和邊集分別用V(G)和E(G)來表示.設(shè)v ∈ V(G),則點v在G中的度數(shù)表示為dG(v),圖G的最大度和最小度分別表示為 △(G)和 δ(G).定義 σ2(G)= min{d(x)+ d(y)|x,y ∈ V(G),xy(?)E(G)}.稱k個圖是可填裝的,如果它們可嵌入到一個完全圖中使得其中任意兩個是邊不交的.若= 2則稱為2-填裝,圖中點不交的子圖問題是一類特殊的2-填裝問題.G的一個完全子圖被稱為團,若一個團中包含的頂點數(shù)為kk,那么稱其為k-團.1963年,Erdos提出了一個關(guān)于圖中包含k個點不交團的猜想.令G是一個頂點數(shù)為n的圖,滿足n= sk,s和k為正整數(shù)且s ≥ 3,k ≥ 1.若δ(G)≥(s-1)k,則G含有k個點不交的Ks.當(dāng)s = 4時,1978年Bollobos證明了:令G是一個頂點數(shù)為n的圖,其中n = 4k,k為正整數(shù).若滿足δ(G)≥3n/4,那么G包含k個獨立的4-團.最近,Wang證明了:假設(shè)δ(G)≥[n/2],那么G包含k個獨立的圈,其...

【文章頁數(shù)】：53 頁

【學(xué)位級別】：碩士

【文章目錄】：
中文摘要
英文摘要
符號說明
第一章 前言
    §1.1 基本概念
    §1.2 問題產(chǎn)生的背景及其發(fā)展近況
第二章 圖中具有指定性質(zhì)的不交團
    §2.1 預(yù)備知識及定理
    §2.2 主要引理
    §2.3 主要定理證明
第三章 二部圖中最大個數(shù)的獨立圈
    §3.1 預(yù)備知識及定理
    §3.2 主要引理
    §3.3 主要定理證明
參考文獻
致謝
已發(fā)表的論文
附件



本文編號：3744377