本文選題：內(nèi)劃分　切入點：對分　出處：《中國科學(xué)技術(shù)大學(xué)》2017年碩士論文

【摘要】：圖的內(nèi)劃分問題是圖論的劃分問題中一個有趣的待解決的問題。圖的內(nèi)劃分是指將有限圖G =(V,E)的頂點集V劃分為兩個非空的部分,使得每個部分的頂點在自己所在部分中有至少一半的鄰點。相比于圖的內(nèi)劃分問題,傳統(tǒng)的圖論研究方面更多解決的是圖的外劃分問題以及各種割邊問題。而對于圖內(nèi)劃分的存在性,以及何種圖類具有內(nèi)劃分,還有內(nèi)劃分中特殊的對分情況,在較多的情形下仍然是懸而未決的。很多時候要找到對一固定圖類的內(nèi)劃分或是構(gòu)建不存在內(nèi)劃分的極圖都是相當(dāng)困難的任務(wù)。而由于內(nèi)劃分其應(yīng)用的廣泛,不僅在數(shù)學(xué)理論研究領(lǐng)域下,在不少經(jīng)濟(jì)學(xué)領(lǐng)域與社會學(xué)領(lǐng)域下的研究也與內(nèi)劃分問題有所關(guān)聯(lián),因此研究內(nèi)劃分問題是極有意義的。目前已經(jīng)有不少研究內(nèi)劃分問題的文章,DeVos提出了著名的關(guān)于內(nèi)劃分的猜想:對于每一個d-正則圖,存在一個與之相關(guān)的整數(shù)N(d),當(dāng)圖的頂點數(shù)n大于N(d)時,形如([d/2],[d/2])的內(nèi)劃分是存在的。本文從三個方面去分析了有限圖的內(nèi)劃分問題:相關(guān)工作,主要定理與其他的研究。本文先是介紹了內(nèi)劃分問題的由來與背景,著重介紹了關(guān)于Thomassen與Stiebitz在內(nèi)劃分問題上所作的開創(chuàng)性工作。然后是本文的主要工作:一個圖G =(V,E)的(s,t)-劃分,是指將圖的頂點集V劃分為V1與V2兩個子集使得對于各自誘導(dǎo)子圖的最小度滿足δ(G[V1])≥s與δ(G[V2])≥t,這是DeVos內(nèi)劃分猜想的弱形式。文中證明了當(dāng)圖的頂點度d∈ {5,7,9}的情形下,頂點數(shù)至少為N(d)的d-正則圖一定存在([d/2],[d/2])一劃分,并給出對應(yīng)情形下的圖的階數(shù)N(d)的下界,此外還給出了部分情況的極圖。之后本文介紹了與內(nèi)劃分密切相關(guān)的外劃分與對分的一些研究,包含了 Ban與Linial在補圖與立方圖上的內(nèi)劃分的一些推導(dǎo)。最后,本文還對一些內(nèi)劃分問題的挑戰(zhàn)作出討論,并試著去探討一些研究方向與思路。
[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