论文部分内容阅读
图论的产生和发展经历了二百多年的历史,它是组合数学的一个重要分支. 本文把不含环和重边的无向有限图称为简单图,无爪图是简单图中的一种.如果图G中不包含同构于K1,3的导出子图,则称这样的图为无爪图.K4表示从K4中删掉任意一条边所得到的图.设G是阶数为n且最小度为δ的无爪图,我们给出了G中包含的点不交K-4的个数与δ以及n之间的关系. 如果图的阶数是非空的并且相关联的两顶点之间的边数是有限的,则称为多重图,多重图中每条边的重数至多是2且不包含环,则称之为标准多重图,记为M.把长度为4的圈称为四边形.定义D是阶数为4κ的有向图且κ是非负整数,设有向图D的最小度δ≥6κ-2,则D包含κ个点不交有向四边形,除了图D同构一类特殊图以外. 本文主要考虑了以下几个问题:无爪图中点不交子图的存在性,多重图中点不交的四边形. 全文共有四章.第一章介绍了图的基本概念及所研究问题的历史背景和发展情况. 第二章主要研究了无爪图中点不交K4.主要结论如下:设G是阶数为n,最小度δ≥5的无爪图,则G至少包含F(n,δ)=(δ-4/7δ-8)n个点不交的K-4. 第三章主要研究了多重图中点不交的四边形.主要结论如下:设M是顶点数为4κ的标准多重图,κ是非负的整数,如果δ(M)≥6κ-2,那么M包含κ个点不交的Q47,除了M∈{(D)*,(F)*}. 最后,本文的每章末尾均提出了一个问题,以待进一步讨论和研究.