竞赛图中的点不交圈问题

论文摘要

本文研究竞赛图中满足一定最小出度条件的点不交4-圈问题.这篇文章只考虑有向图,除非特殊说明,否则下文提到的圈都是有向圈.令G是一个有向图,V（D）表示它的顶点集,A（D）表示它的弧集.称圈C是一个q-圈,如果|V（C）==q.令T是一个有向图,如果对T中任意两个不同顶点χ和y.恰有（χ,y）或者（y.χ）中的一条弧属于A（T）,则称T是一个竞赛图,设v e V（T）.则点v在T中的出度表示为d+（v）,图T的最小出度表示为δ+（T）.1981年.Bermond和Thomassen提出了一个猜想:对≥ 1,任一最小出度至少为2κ-1的有向图包含κ个点不交的有向圈.当κ=1时,这个猜想是显然成立的.1983年,Thomassen证明了κ=2的情况.κ=3的情况由Lichiardopol,Por和Sereni给出了证明,这个猜想仍然没有完全解决.2014年,Jorgen Bang-Jensen,Bessy和Thomasse证明了这个猜想在竞赛图的情况下是成立的.2010年,Lichiardopol提出了一个关于特定长度不交圈的猜想:对给定的整数q≥3和κ≥1,任一满足最小出度至少为（q-l）κ-1的竞赛图T都包含κ-个不交的q-圈.Lichiardopol本人证明了最小出度和最小入度都至少为（q-1）--1的情况,2018年,F.Ma和J.Yan在此基础上提高了此结果.受此猜想的启发,本文研究了q=4的情况,证明了如下结果:结果1:对于给定的整数κ≥1,如果T是一个满足δ+（T）≥ 3κ-1的竞赛图,则T至少包含κ个点不交的4-圈.结果1可由一个更强的结论直接推出:结果2:对于给定的整数κ≥ 1,如果T是一个满足δ+（T）≥ 3k-1的竞赛图.那么对T的每个包含κ-1个不交4-圈的集合F,都存在一个包含κ个不交4-圈的集合F’,使得F’交T-于至多7个点.

论文目录

• 中文摘要
• 英文摘要
• 符号说明
• 第一章 前言
•   §1.1 基本概念
•   §1.2 问题产生的背景及其历史发展
• 第二章 竞赛图中的点不交4-圈
•   §2.1 预备知识与定理
•   §2.2 引理
•   §2.3 主要定理的证明
• 第三章 可进一步研究的问题
• 参考文献
• 致谢
• 学位论文评阅及答辩情况表

文章来源

类型: 硕士论文

作者: 朱硕

导师: 颜谨

关键词: 竞赛图,最小出度,点不交圈,有向图

来源: 山东大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 山东大学

分类号: O157.5

总页数: 44

文件大小: 1863K

下载量: 14