有限图的内划分问题

发布时间：2018-03-24 13:09

  本文选题：内划分　切入点：对分　出处：《中国科学技术大学》2017年硕士论文

【摘要】：图的内划分问题是图论的划分问题中一个有趣的待解决的问题。图的内划分是指将有限图G =(V,E)的顶点集V划分为两个非空的部分,使得每个部分的顶点在自己所在部分中有至少一半的邻点。相比于图的内划分问题,传统的图论研究方面更多解决的是图的外划分问题以及各种割边问题。而对于图内划分的存在性,以及何种图类具有内划分,还有内划分中特殊的对分情况,在较多的情形下仍然是悬而未决的。很多时候要找到对一固定图类的内划分或是构建不存在内划分的极图都是相当困难的任务。而由于内划分其应用的广泛,不仅在数学理论研究领域下,在不少经济学领域与社会学领域下的研究也与内划分问题有所关联,因此研究内划分问题是极有意义的。目前已经有不少研究内划分问题的文章,DeVos提出了著名的关于内划分的猜想:对于每一个d-正则图,存在一个与之相关的整数N(d),当图的顶点数n大于N(d)时,形如([d/2],[d/2])的内划分是存在的。本文从三个方面去分析了有限图的内划分问题:相关工作,主要定理与其他的研究。本文先是介绍了内划分问题的由来与背景,着重介绍了关于Thomassen与Stiebitz在内划分问题上所作的开创性工作。然后是本文的主要工作:一个图G =(V,E)的(s,t)-划分,是指将图的顶点集V划分为V1与V2两个子集使得对于各自诱导子图的最小度满足δ(G[V1])≥s与δ(G[V2])≥t,这是DeVos内划分猜想的弱形式。文中证明了当图的顶点度d∈ {5,7,9}的情形下,顶点数至少为N(d)的d-正则图一定存在([d/2],[d/2])一划分,并给出对应情形下的图的阶数N(d)的下界,此外还给出了部分情况的极图。之后本文介绍了与内划分密切相关的外划分与对分的一些研究,包含了 Ban与Linial在补图与立方图上的内划分的一些推导。最后,本文还对一些内划分问题的挑战作出讨论,并试着去探讨一些研究方向与思路。
[Abstract]:The problem of the inner partition of a graph is an interesting problem to be solved in graph theory. The inner partition of a graph means that the vertex set V of a finite graph G / V (E) is divided into two non-empty parts. So that the vertices of each part have at least half the adjacent points in their part. In traditional graph theory research, many problems are solved, such as the problem of outer partition of graph and the problem of cutting edge, but for the existence of partition in graph, which class of graph has inner partition, and the special case of inner partition. In many cases it is still a pending task. It is very difficult to find an inner partition for a fixed graph class or to construct a pole graph that does not exist, and because of its wide application, Not only in the field of mathematical theory, but also in many fields of economics and sociology, the research is related to the problem of internal division. So it is very meaningful to study the problem of internal partitioning. DeVos has put forward a famous conjecture about inner partition for every dregular graph. There is a related integer N n D T, and when the number of vertices n of a graph is greater than n n n, there exists an inner partition in the form of ([d / 2], [d / 2]). In this paper, we analyze the problem of the inner partition of finite graphs from three aspects: related work, This paper first introduces the origin and background of the inner partition problem, and emphasizes the pioneering work on the inner partition problem between Thomassen and Stiebitz. The vertex set V of a graph is divided into two subsets V1 and V2 such that the minimum degree of each induced subgraph satisfies 未 G [V1] 鈮，

本文编号：1658441