二部平衡公平划分的一个下界

设V_1,V_2是图G的一个二部划分.如果一1≤|V_1|-|V_2|≤1,则称V_1,V_2是G的一个二部平衡划分.对于n个顶点m条边的简单图G,本文证明了:(1)若G是k-正则图(k≥3),则G存在一个最小二部平衡划分V_1,V_2,使得max{e(V_1),e(V_2)}≥((k-1)m)/4k;(2)如果r是大于4的实数,且当n是偶数时△(G)≤((3r-4))/(r+4)δ(G)-(2r)/(r+4),当n是奇数时△(G)≤(3r-4)/(r+4)δ(G)-(8r)/(r+4),那么G存在一个二部平衡划分,使得min{e(V_1),e(V_2)}≥m/r,这里e(V_i)表示G中两个顶点都在V_i中的边的数目.     

平面图最小平衡二部划分的上界

关于平面图的平衡二部子图的研究有一个猜想:任意一n个顶点的平面图G(V,E),必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.证明了若n个顶点的哈密尔顿平面图G(V,E)中含有一个近似等边三角形,n≥18,那么G(V,E)必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.     

哈密尔顿平面图最小平衡二部划分的上界

设G(V,F)是一个图,V_1,V_2是V的一个二部划分,用e(V_1,V_2)表示一条边的两个端点在不同划分里边的总数目,当‖V_1|-|V_2‖≤1时,称V1,V2是V的一个平衡二部划分。最小平衡二部划分是指寻找G(V,F)的一个平衡二部划分使得e(V1,V2)最小。对于哈密尔顿平面图G(V,F),研究了当Perfect-内部三角形最大边函数值与最小边函数值之差为d时,e(V_1,V_2)最小值的上界与d之间的关系。     

最大度与最小度相差不超过2的图的平衡judicious划分

图G的顶点集V(G)的一个二部划分V_1和V_2叫做平衡二部划分,如果||V_1|-|V_2||≤1成立.Bollobas和Scott猜想:每一个有m条边且最小度不小于2的图,都存在一个平衡二部划分V_1,V_2,使得max{e(V_1),e(V_2)}≤m/3,此处e(V_i)表示两顶点都在V_i(i=1,2)中的边的条数.他们证明了这个猜想对正则图(即△(G)=δ(G))成立.颜娟和许宝刚证明了每个(k,k-1)-双正则图(即△(G)-δ(G)≤1)存在一个平衡二部划分V_1,V_2,使得每一顶点集的导出子图包含大约m/4条边.这里把该结论推广到最大度和最小度相差不超过2的图G.     

哈密尔顿平面图最小平衡二部划分的上界

设$G（V，E）$是一个图，$V_{1}，V_{2}$是$V$的一个二部划分，用$e（V_{1}，V_{2}）$表示一条边的两个端点在不同划分里边的总数目，当$||V_{1}|-|V_{2}||\leq 1$时，称$V_{1}，V_{2}$是$V$的一个平衡二部划分。最小平衡二部划分是指寻找$G（V，E）$的一个平衡二部划分使得$e（V_{1}，V_{2}）$最小。对于哈密尔顿平面图$G（V，E）$，研究了当Perfect-内部三角形最大边函数值与最小边函数值之差为$d$时，$e（V_{1}，V_{2}）$最小值的上界与$d$之间的关系。     

二部图中的独立6-圈

本文主要证明了对二部图G=(V_1,V_2,E),|V_1|=|V_2|=3k,其中k为正整数.若G的最小度至少为2k-1,则G至少包含k-1个独立6-圈.     

二部图上完美匹配的正交匹配分解

给定简单二部图G=（V，E），最大度是k（k≥3），G有一个完美匹配M={e1，e2，…，ek}。称边集E的划分{E1，E2，…，El}是G的一个关于肼的正交匹配分解，如果对每一个El是G的匹配并且包含且仅包含肼中的一条边。在本文中我们将证明对于简单二部图G，存在关于完美匹配肼的正交匹配分解，并给出了求这个分解的多项式时间算法。     

均衡二部图中含2k条指定边的k个独立圈及2-因子

得到了对于二部图G=(V_1,V_2;E),当|V_1|=|V_2|=n≥2k+1时的结果:对G中任意2k条独立边e_1,e_1~*,…,e_k,e_k~*,G中一定存在k个独立的4-圈C_1,C_2,…,C_k,使得对任意i∈{1,2,…,k}有{e_i,e_i~*}E(C_i).并在此基础上进一步证明了当|V_1|=|V_2|=n≥3k时若对任意两顶点x∈V_1,y∈V_2,都有d(x)+d(y)≥2n-k+1成立,则G有一个2-因子含有k+1个独立圈C_1,C_2,…,C_(k+1)使得对任意i∈{1,2,…,k}有{e_i,e_i~*}E(C_i)且|C_i|=4.     

极大3限制边连通二部图的充分条件

设G=(V,E)是一个连通图.称一个边集合S■E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点.称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λ_k(G).定义ξ_k(G)=min{[X,■]:|X|=k,G[X]连通,■=V(G)\X}.称图G是极大k限制边连通的,如果λ_k(G)=ξ_k(G).本文给出了围长为g>6的极大3限制边连通二部图的充分条件.     

二部图是可迹的一个充分条件

本文证明了以下结果:设G=(X,Y;E)是连通的二部图,如果4≤|Y|≤|X|≤|Y|+1,且NC_2≥|X|-1,则G是可迹的。从而表明[2]中的猜想对二部图是成立的。