图中点不交圈的相关问题

发布时间：2023-02-16 19:38

　　在此论文中,主要介绍图中一定条件的不交团及独立的圈在一些二分图中的相关结果.本文令G代表一个图,它的顶点集和边集分别用V(G)和E(G)来表示.设v ∈ V(G),则点v在G中的度数表示为dG(v),图G的最大度和最小度分别表示为 △(G)和 δ(G).定义 σ2(G)= min{d(x)+ d(y)|x,y ∈ V(G),xy(?)E(G)}.称k个图是可填装的,如果它们可嵌入到一个完全图中使得其中任意两个是边不交的.若= 2则称为2-填装,图中点不交的子图问题是一类特殊的2-填装问题.G的一个完全子图被称为团,若一个团中包含的顶点数为kk,那么称其为k-团.1963年,Erdos提出了一个关于图中包含k个点不交团的猜想.令G是一个顶点数为n的图,满足n= sk,s和k为正整数且s ≥ 3,k ≥ 1.若δ(G)≥(s-1)k,则G含有k个点不交的Ks.当s = 4时,1978年Bollobos证明了:令G是一个顶点数为n的图,其中n = 4k,k为正整数.若满足δ(G)≥3n/4,那么G包含k个独立的4-团.最近,Wang证明了:假设δ(G)≥[n/2],那么G包含k个独立的圈,其...

【文章页数】：53 页

【学位级别】：硕士

【文章目录】：
中文摘要
英文摘要
符号说明
第一章 前言
    §1.1 基本概念
    §1.2 问题产生的背景及其发展近况
第二章 图中具有指定性质的不交团
    §2.1 预备知识及定理
    §2.2 主要引理
    §2.3 主要定理证明
第三章 二部图中最大个数的独立圈
    §3.1 预备知识及定理
    §3.2 主要引理
    §3.3 主要定理证明
参考文献
致谢
已发表的论文
附件



本文编号：3744377