关于二部图中弦圈的几个结果

发布时间：2020-10-30 22:11

【摘要】：图论作为离散数学的一个分支,至今已有二百多年的历史.近年来,图论在科学界异常活跃,应用图论来解决计算机科学、生物学、化学等学科的问题已经显示出了很大的优越性.不含环和重边的无向有限图称为简单图.本文所涉及的图均指简单无向有限图.本文主要考虑两个问题:二部图中含特定点的点不交弦圈的最小度条件;二部图中包含点不交的双弦圈的最小度条件.设G =(V,E)是一个无向图,如果顶点集V可以分割成两个互不相交的子集V1和V2,并且图中的每条边都是V1中的一点与V2中的一点相连得到的,则称图G为二部图.弦是指连接圈上的两个点构成的一条边,使得这条边不属于圈上.如果一个圈至少有一条弦,那么我们称这个圈为弦圈.如果一个圈至少有两条弦,那么我们称这个圈为双弦圈.本文共分为三个部分.第一部分介绍了图的基本概念以及所研究问题的历史背景和发展情况.第二部分主要研究了二部图中含特定点的点不交弦圈的最小度条件.主要结论为:设G =(V1,V2;E)是一个二部图,且|V1= |V2| = n ≥ 12k-4,其中k为任意的正整数.如果δ(G)≥n+1/2,则对G的任意k个不同的点u1,…,uk,G中存在k个点不交的弦圈C1,…,Ck,使得任意的1 ≤ i ≤ k,ui∈ V(Ci)且6≤|Ci| ≤ 8.第三部分主要研究了二部图中包含点不交的双弦圈的最小度条件.主要结论为:令G =(V1,V2;E)是一个二部图,且|V1| = |V2| ≥ 3k,其中k为任意的正整数.如果δ(G)≥2k+1,则G包含k个不交的双弦圈.
【学位授予单位】：宁夏大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5
【文章目录】：
摘要
ABSTRACT
主要符号对照表
第一章 引言
    1.1 基本概念和术语
    1.2 问题的研究背景
    1.3 已有结论及本文的结果
第二章 二部图中过特定点的点不交的弦圈
    2.1 基本概念及术语
    2.2 主要定理1.3.5的证明
    2.3 可进一步讨论的问题
第三章 二部图中点不交的双弦圈
    3.1 预备知识
    3.2 主要引理
    3.3 主要定理1.3.10的证明
参考文献
致谢
个人简介

【参考文献】

中国期刊全文数据库 前2条

1 朱莎;郝荣霞;;二部图中的独立6-圈(英文)[J];数学进展;2007年05期

2 颜谨,刘桂真;图中相互独立的4-圈和含4个点的路[J];数学物理学报;2003年06期

本文编号：2863065