关于图中相互独立的圈和2-因子的新结果

论文摘要

本文考虑的图若无特殊声明均为简单、无向有限图，对于一个图G=G（V（G），E（G）），我们用V（G）和E（G）分别表示图的顶点集合和边集合．对任意的v∈V（G），我们用dG（v）表示顶点v在G中的度数．△（G）和δ（G）分别表示图G的最大度和最小度，在不引起混淆的情况下简记为△和δ。对于图G，我们用|G|=|V（G）|表示G的阶数，即G的顶点数，并定义图G中两个不相邻的顶点的最小度和为：σ2（G） = min{dG（x）+dG（y）|x,y∈V（G）,x≠y,xy （?） E（G）}（若G是一个完全图，则令σ2（G）=∞）．对图G中任意点u，u的邻域定义如下：NG（u） = {x∈V（G）|xu∈E（G）}．完全二部图K1,3称为一个爪，如果G不含同构于K1，3的生成子图，则称G是无爪图．对于图G中的一条路P和一个圈C，定义路和圈的长度分别为：l（P） = |V（P）| - 1, l（C） = |V（C）|．G的一个哈密顿圈是G的包含G中所有顶点的一个圈．G的一个1-因子是G的一个1-正则支撑子图，通常我们称1-因子为完美对集或完美匹配．显然G的一个1-因子是覆盖G的所有顶点的一个边集合。G的一个2-因子是G的一个2-正则支撑子图，易见2-因子的每一个连通分支为一个圈．图的k个独立圈是指G中k个顶点不相交的圈．图的独立圈、2-因子问题是图的因子理论中非常重要的一部分，也是图的哈密顿圈理论的推广和延伸．它是图论中非常有趣的一类问题，其理论研究日益成熟和完善，而且它在计算机科学、通信网络设计等中都有重要应用。关于图的独立圈、2-因子的研究主要集中在以下几个方面：图中含指定个数的独立圈和2-因子，含指定长度的独立圈和2-因子和图中具有指定性质的独立圈和2-因子等等。全文共分三章。第一章简单介绍了图论的基本概念，圈和因子的历史和发展状况及一些已有的相关结论。这一章是第二章和第三章的基础．在本文的第二章中，我们研究了图中含指定长度的相互独立的圈问题，颜谨[17]证明了下面的的结论：如果G是一个简单图，s，k是两个正整数并且s≤k，其中G的顶点个数n≥3s+4（k-s）+3．如果σ2（G）≥n+s，那么G包含k个顶点不相交的圈C1,…，Ck并且|Ci|=3其中1≤i≤s，|Ci|=4其中s<i≤k。在第二章中我们则有以下结论：定理2．1．1．如果G是一个简单图，s，k是两个正整数并且s≤k，其中G的顶点个数n≥3s+4（k-s）+3。如果σ2（G）≥n+2k-s+3/2，那么G包含k个顶点不相交的圈C1，…，Ck并且|Ci|=3其中1≤i≤s，|Ci|=4，|E（Ci）|≥5其中s<i≤后．第三章我们则讨论了图中含指定边和指定长度的图的2-因子的问题．其主要结果如下：定理3．1．1．设G是一个有n1+n2+1个顶点的简单图，其中n1≥3，n2≥3．若δ（G）≥（?）3n1/4（?）+（?）3n2/4（?）+1，那么G包含两个顶点不相交的圈C1，C2，其中|C1|=ni+1，|C2|=nj（i，j=1，2），并且（?）e∈G我们有e∈E（C1）或e∈E（C2）。

论文目录

• 中文摘要
• 英文摘要
• 符号说明
• 第一章 引言
• §1.1 基本概念
• §1.2 问题产生的背景
• §1.3 本文的主要结果
• 第二章 图中含指定长度的相互独立的圈
• §2.1 相关结论及本章结果
• §2.2 定理证明
• §2.3 可进一步讨论的问题
• 第三章 图中含指定边和指定长度的图的2-因子
• §3.1 图中含指定边和指定长度的2-因子的相关结果
• §3.2 引理证明
• §3.3 定理证明
• §3.4 可进一步讨论的问题
• 参考文献
• 致谢
• 作者简介
• 学位论文评阅及答辩情况表