图上关于点不交四阶子图的若干结果
发布时间：2018-08-15 16:27
【摘要】：图论的产生和发展经历了二百多年的历史,它是组合数学的一个重要分支.本文把不含环和重边的无向有限图称为简单图,无爪图是简单图中的一种.如果图G中不包含同构于K1,3的导出子图,则称这样的图为无爪图.K4-表示K4中删掉任意一条边所得到的图.设G是阶数为n且最小度为δ的无爪图,我们给出了G中包含的点不交K4-的个数与δ以及n之间的关系.如果图的阶数是非空的并且相关联的两顶点之间的边数是有限的,则称为多重图,多重图中每条边的重数至多是2且不包含环,则称之为标准多重图,记为M.把长度为4的圈称为四边形.定义D是阶数为4k的有向图且k是非负整数,设有向图D的最小度δ≥6k-2,则D包含k个点不交有向四边形,除了图D同构一类特殊图以外.本文主要考虑了以下几个问题：无爪图中点不交子图的存在性,多重图中点不交的四边形.全文共有四章.第一章介绍了图的基本概念及所研究问题的历史背景和发展情况.第二章主要研究了无爪图中点不交K4-.主要结论如下：设G是阶数为n,最小度δ≥5的无爪图,则G至少包含F(n,δ)=(δ-4)(7δ-8)n个点不交的K4-第三章主要研究了多重图中点不交的四边形.主要结论如下：设M是顶点数为4k的标准多重图,k是非负的整数,如果δ(M)≥6k-2,那么M包含k个点不交的Q74,除了M∈{D*,F*}.最后,本文的每章末尾均提出了一个问题,以待进一步讨论和研究.
[Abstract]:Graph theory has experienced more than 200 years of history, and it is an important branch of combinatorial mathematics. In this paper, an undirected finite graph with no ring and double edges is called a simple graph, and a claw free graph is one of the simple graphs. If a graph G does not contain an derived subgraph which is isomorphic to K1 + 3, then it is called a claw-free graph. K4- denotes the graph obtained by deleting any edge in K4. Let G be a claw free graph of order n and minimum degree 未. We give the relationship between the number of disjoint K4- points contained in G and 未 and n. If the order of a graph is nonempty and the number of edges between two associated vertices is finite, then it is called a multiplex graph. The multiplicity of each edge in a multiplex graph is at most 2 and does not contain a ring. A circle of 4 is called a quadrilateral. It is defined that D is a directed graph of order 4k and k is a non-negative integer, and the minimum degree 未 鈮，
本文编号：2184764
[Abstract]:Graph theory has experienced more than 200 years of history, and it is an important branch of combinatorial mathematics. In this paper, an undirected finite graph with no ring and double edges is called a simple graph, and a claw free graph is one of the simple graphs. If a graph G does not contain an derived subgraph which is isomorphic to K1 + 3, then it is called a claw-free graph. K4- denotes the graph obtained by deleting any edge in K4. Let G be a claw free graph of order n and minimum degree 未. We give the relationship between the number of disjoint K4- points contained in G and 未 and n. If the order of a graph is nonempty and the number of edges between two associated vertices is finite, then it is called a multiplex graph. The multiplicity of each edge in a multiplex graph is at most 2 and does not contain a ring. A circle of 4 is called a quadrilateral. It is defined that D is a directed graph of order 4k and k is a non-negative integer, and the minimum degree 未 鈮，
本文编号：2184764
本文链接：https://www.wllwen.com/kejilunwen/yysx/2184764.html
