论文部分内容阅读
设G是一个简单图.如果我们将G的顶点集V(G)划分成2个非空且互不相交的顶点集V1,V2,则称(V1,V2)是图G的一个划分.若G的划分(V1,V2)满足条件||V1|-|V2||≤1,则(V1,V2)被称为G的一个平衡划分.很显然,没有任何附加要求的划分问题是没有意义的.本文主要讨论两种不同类型的平衡划分问题:一种是带边数条件限制的,一种是带点度条件限制的.在[8]中,Bollobas和Scott提出了一个猜想:若G是最小度大于等于2的图,则G存在平衡划分(S,S)满足:max{e(S),e((?))} ≤1/3m(G),其中e(S)表示S导出的子图的边数.Lee, Loh和Sudakov [17]证明了 :若G是一个简单图,最小度是2k或2k 1,则G存在平衡划分(S,S)满足:max{e(S),e((?))} ≤k+1/2(2k+1)+o(1))m(G),并且他们猜想无穷小的尾数项可以去掉.2014年,Xu和Yu [29]证明了上面提到的Bollobs和Scott的猜想.这让我们想知道:在Lee, Loh和Sudakov的结果中,当k = 2时,无穷小的尾数项是否可以去掉.即:若G是一个简单图且最小度大于等于4, G是否存在平衡划分(S,S)满足:max{e(S),e((?))}≤3/10m(G).容易验证对点数少的图而言,Lee, Loh和Sudakov的猜想在k = 2时是对的.由此我们试图通过研究极小反例的结构性质来证明这一猜想.在这个过程中我们得到了以下结论:定义X = {G : δ(G) ≥ 4, G的任一平衡划分(S,S)满足:max{e(S),e((?))} >3/10e(G)},设G是X中点数最少的.若G中有四个4度顶点v1,v2,v3,v4满足G[v1,v2,v3, v4](?)K4则((?)N(vi)\{v1,v2,v3,v4})|≠3,4;若|(?)N(vi)\{v1,v2,v3,v4})| = 2,则除非n是偶数且m模10的余数是3,否则图不是G的子图;除非n是偶数且m模10的余数是3,或6,或9,否则图2不是G的子图.本学位论文的第二个主要结论是关于点度限制下的平衡划分问题.若图G的一个划分(A,B)满足:A中的点在A中的邻点数不小于其在B中的邻点数且B中的点在B中的邻点数不小于其在A中的邻点数,则称(A:B)是G的一个内部划分.2014年,Liu和Xu [19]证明了 :每一个最小度d≥2的图G都有(1,1)—平衡划分(S,S)满足:δ(S) + δ((?))≥ d - 1.我们利用文献[18]的思想得到下面的结论:设d ≥5, G是d-正则图.若G没有内部划分,则G存在(2,2)-平衡划分(S,S)满足:δ(S)+δ((?))≥ d - 1.