关于图的弦圈和无爪图的一些结果

摘要

图论的研究开始于200多年前。关于图论的第一篇论文是Euler于1736年发表的。他用图的方法解决了哥尼斯堡Konigsberg七桥问题。自从二十世纪六十年代以来，图论在科学界非常活跃。应用图论来解决计算机科学、生物学、化学等学科的问题已经显示出了很大的优越性。图论是离散数学的一个分支，近年来受到了各界的重视。
　　 一个图G=G(V, E)，用V(G)表示图G的顶点的集合，用E(G)表示图G的边的集合。本文考虑不含环及重边的无向有限图。对于一点V，我们用dG(v)表示顶点v在图G中的度数，用δ(G)表示图G的最小度。图的路径是指图的点边交替有限非空序列，若该序列中点不重，则称作路。首尾相接的路称为圈。图的Hamilton圈是指图中过每个点的圈。图的Hamilton圈问题，是图论中一个非常著名的问题。
　　 本文主要研究了图论中的几个问题。全文共分为三章。第一章我们介绍了图论及图论中圈的发展。首先是图论的发展历史，然后是基本的定义及术语，最后是圈的发展情况。第二章我们对图中含两个圈的2-因子问题进行了扩展，研究了图中覆盖整个图的两个不交弦圈的存在性问题，在一定度条件下给出了证明，并讨论了它的最优性。第三章我们对无爪图的两个圈的2-因子进行了研究，我们用反例说明了在2-因子存在的情况下两个圈的2-因子圈长不是任意的。最后对无爪图中点的邻域进行了研究。
　　 本文的核心部分主要是讨论了这样的一个问题:定理2.3令G表示n1+n2(ni≥4，i=1，2)个顶点的简单图，如果G的最小度，δ(G)≥1/2n1+1/2n2+1，那么G包含两个长度分别为n1和n2的独立弦圈G1和G2。
　　 我们有反例说明此定理的条件是最优的。
　　 第三章主要给出了一类反例和如下两个定理:
　　 定理3.1图G是无爪图，点u∈V(G)的邻域记作N（u）。H=G[N（u）∪{u}]，则H的独立数不小于2。若H的连通度κ（H）≥2，那么H是哈密尔顿图。
　　 定理3.2图G是无爪图，点u∈V(G)的邻域记作N(u)。H=G[N(u)∪{u}]，则H的独立数不大于2。若H的连通度κ（H）=1，那么H是两个完全图的并。
　　 而本文讨论的问题主要是来源于El-Zahar猜想，猜想2.5设G是一个简单图，其顶点数n=n1+n2+…+nk(ni≥3)。如果δ(G)≥[n1/2]+[n2/2]+…+[nk/2]，那么G中包含k个独立圈C1，C2，…,Ck，其长度分别为n1，n2，…，nk。

目录

声明

摘要

符号说明

第一章 图论简介

§1．1 图论的产生与发展

§1．2 图论的基本概念

§1．3 图的圈理论的发展

第二章 图的含弦2-因子

§2．1 主要结论及证明

§2．2 最优性说明及可以进一步讨论的问题

第三章 无爪图的圈问题

§3．1 两个圈的二因子

§3．2 无爪图中含圈的邻域性条件

§3．3 可以进一步考虑的问题

参考文献

致谢