标准多重图中关于点不交子图的若干结果

发布时间：2018-03-30 20:10

本文选题：点不交　切入点：度条件　出处：《宁夏大学》2017年硕士论文

【摘要】：图论是组合数学的一个分支,在各个领域有着广泛的应用,受到了数学界和其他科学界的重视.本文主要考虑了两个问题:标准多重二部图中点不交的4圈的存在性度条件;标准多重图中点不交的重边四边形.本文所指的有向图为无环无重边的简单有限有向图.不含环和重边的无向有限图称为简单图,顶点集非空且任意两个顶点之间的边数有限的图称为多重图,任意两个顶点之间边数至多为2的多重图称为标准多重图.长为4的圈称为4圈或者四边形,圈上的四条边都为重边的四边形称为重边四边形.本文分为四个部分.第一部分介绍了图的基本概念以及所研究问题的历史背景和发展情况.第二部分研究了对于标准多重二部图M =(X,Y;E),满足|X| = |Y| = 2k,k为正整数.如果M中每个点的度数至少为3k + 1,则M 一定包含k个点不交的4圈,使得其中k-1个为重边四边形,剩余一个四边形至少有三条重边.作为推论,我们给出了简单二部图和简单有向二部图中点不交的存在性度条件.第三部分主要研究了对于阶数为4k,最小度为6k-2的标准多重图,k为正整数,除三个特例外,M包含k-1个重边四边形和一个有三条重边的四边形,使得这k个四边形彼此点不交.最后提出了一些问题,以待进一步讨论和研究.
[Abstract]:Graph theory is a branch of combinatorial mathematics, which has been widely used in various fields and has been paid attention to by mathematics and other scientific circles. In this paper, two main problems are considered: the existence degree condition of 4 cycles with disjoint points in standard multipartite graphs; The digraph in this paper is a simple finite directed graph with no ring and no multiplicity. An undirected finite graph without ring and reborder is called a simple graph. A graph with a nonempty vertex set and a finite number of edges between two vertices is called a multiplex graph, a multiplex graph with at most 2 edges between any two vertices is called a standard multiplex graph, and a cycle of 4 is called a 4 cycle or a quadrilateral. This paper is divided into four parts. The first part introduces the basic concept of graph and the historical background and development of the problem studied. If X = Y = 2kW k is a positive integer, if the degree of each point in M is at least 3k1, then M must contain 4 cycles with k points disjoint. Such that k-1 is a quadrilateral with a heavy edge, and the remaining quadrilateral has at least three heavy edges. As a corollary, In this paper, we give the existence conditions of disjoint points in simple bipartite graphs and simple directed bipartite graphs. In the third part, we mainly study that the standard multifold graphs with order 4k and minimum degree 6k-2 are positive integers. With the exception of three special exceptions, M contains k-1 double quadrilateral and one quadrilateral with three heavy edges, such that the k quadrilateral does not intersect with each other. Finally, some problems are proposed for further discussion and study.
【学位授予单位】：宁夏大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】