均衡二部图中含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.     

不含5-圈和相邻6-圈的平面图的全染色

图的正常k-全染色是用k种颜色给图的顶点和边同时进行染色,使得相邻或者相关联的元素(顶点或边)染不同的染色.使得图G存在正常k-全染色的最小正整数k,称为图G的全色数,用χ″(G)表示.证明了若图G是最大度△≥6且不含5-圈和相邻6-圈的平面图,则χ″(G)=△+1.     

用独立圈对图的一个划分

图G包含4k个点,k≥2,如果σ_2(G)≥4k,则G包含k-2个4-圈和一个8-圈,并且这k-1个圈点不相交.     

图的k部划分的一个注记

设k≥2是一个整数。本文证明了任意有m条边的图都存在一个顶点的划分V_1,V_2…,V_k,使得e(V_1,V_2…,V_k)≥k-1/k m+k-1/2k((2m+1/4)~1/2-1/2)-(k-2)~2/8k,且max{e(V_i):1≤i≤k}≤m/k~2+(k-1)/2k~2((2m+1/4)~1/2-1/2+3/8-7k-4/8k~2.我们的结果改进了[Fan G.,Hou J.,Zeng Q.,A bound for judicious k-partitions of graphs,Discrete Appl.Math.,2014,179:86—99]的主要结论.     

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

设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中的边的数目.     

图中相互独立的4圈和含4个点的路

设k是一个正整数，G是一个顶点数为|G|=4k的图. 假设σ\-2(G)≥4k-1, 则G有一个支撑子图含k-1个4圈和一条顶点数为4的路，使得所有这些圈和路都是相互独立的. 设G=(V\-1,V \-2;E)是一个二分图使得|V\-1|=|V\-2|=2k. 如果对G中每一对满足x∈V\-1和y∈V\-2的不 相邻的顶点x和y 都有d(x)+d(y)≥2k+1, 则G包含k-1个相互独立的4圈和一条顶点数为4的路，使得所有这些圈和路都是相互独立的，并且此度条件是最好的.     

均衡二部图中点不交的4-圈和6-圈（英文）

设G=(V_1,V_2,E)是一个均衡二部图满足|V_1|=|V_2|=n.令δ_(1,1)(G)=min{d(x)+d(y)|x∈V_1,Y∈V_2}.Amar猜想对任意的s个整数(n_1,n_2,…,n_s),n=n_1+n_2+…+n_s,其中n_i≥2.若δ_(1,1)(G)≥n+s,则G含s个点不交的圈,其长分别为2n_1,2n_2,…,2n_s(见[Discrete Math.,1986,58(1):1-10]).本文证明了若一个点数为4k的均衡二部图G满足δ_(1,1)(G)≥2k+4(k≥3),则G含k-3个4-圈和2个6-圈使得所有这些圈都是点不交的.     

超图与图公平划分的l-元组

令S为一个图或超图的某顶点子集,则e(S)表示该图中端点全部在S内的边数. Fan和Hou(2017)证明了每个最大度为?的m阶图G都存在一个k部划分(V_1, V_2,..., V_k),使得对于任意1≤i j≤k,都成立e(V_i∪V_j)min≤{4/k~2×m+4?/k,m/k-1}+o(m~(7/8)).令H表示最大度为?的m阶r-一致超图,本文证明H存在一个k部划分(V_1, V_2,..., V_k),对于任意1≤i j≤k,满足e(V_i∪V_j)≤r-1/k-1×m+o(m);也证明当?=o(m)时, H存在一个k部划分(V_1, V_2,..., V_k),使得对于任意l∈[k-1]和每个l元组(V_(j1),..., V_(jl)),有e(V_(j1)∪···∪V_(jl))≤l~r/k~r/m+o(m).     

不含4-圈和5-圈的平面图的非正常2-染色的一个新结果

设d_1,d_2,···,d_k是k个非负整数,若图G=(V,E)的顶点集V能被剖分成k个子集V_1,V_2,···,V_k,使得对任意的i=1,···,k,V_i的点导出子图G[Vi]的最大度至多为di,则称图G是(d_1,d_2,···,d_k)-可染的,本文证明了既不含4-圈又不含5-圈的平面图是(9,9)-可染的.     

最大亏格、点度和围长

用g(G)和δ(G)分别表示一个图G的围长和顶点最小度. ζ(G)为图G的Betii亏数,主要证明了以下2个结果1)设G为k-边连通简单图,若对G中任意圈C,存在点x∈C满足dG(x)＞|V(G)|/(k-1)2+2)+k-g(G)+2,k=1,2,3,则G是上可嵌入的.且不等式的下界是最好的;2)设G为k-边连通简单图,则ζ(G)≤{max{1,m},k=1,max{1,1/(k-1)m -1}K=2,3 其中m= |V(G)|g(G)-6/g(G)2+(δ(G)-2)g(G)-4'且不等式的上界是可达的.进而得到了最大亏格一个比较好的下界.     

关于拟k-连通图的一个注释

G是一个k-连通图,T是G的一个k-点割,若G-T可被划分成两个子图G₁,G₂,且|G₁|≥2,|G₂|≥2,则称T是G的一个非平凡点割。假定G是一个不含非平凡（k-1）点割的（k-1）-连通图,则称G是一个拟k-连通图。证明了对任意一个k≥5且t> $ \frac{k}{2}$的整数,若G是一个不含（K₂+tK₁）的k-连通图,且G中任意两个不同点对v,w,有d（v）+d（w）≥ $\frac{{3k}}{2} $+t,则对G中的任意一个点,存在一条与之关联的边收缩后可以得到一个拟k-连通图,且G中至少有$\frac{{\left| {V\left( G \right)} \right|}}{2} $条边使得收缩其中任意一条边后仍是拟k-连通的。     

3-γ-临界图G中关于i(G)=γ(G)的一个充分条件

如果图G满足γ（G）＝k且对图G中任两个相邻的点x,y有γ（G＋xy)=k-1,则称图G为k-γ-临界图,如果图G满足γ（G）＝k且对图G中任何距离为d的两点x,y有γ（G＋xy)=k-1,则称图G为k-(γ,d)－临界图。Sumner和Blitch猜想在3－γ－临界图中有γ（G）＝i(G).Oellermann和Swart猜想3－（γ,2）－临界图中有γ（G）＝i(G),这篇文章中我们提出3－γ－临界图中使γ（G）＝i(G)的一个充分条件。     

无爪图中的最长圈

本文证明了:n阶3—连通无爪图G中的最长圈的长至少为min{4k—5,n},这里k是G的最小度.     

点可迁图中的正则因子

设图G是一个K-正则连通点可迁图.如果G不是极大限制性边连通的,那么G含有一个(k-1)-因子,它的所有分支都同构于同一个阶价于k和2k-3之间的点可迁图.此结果在某种程度上加强了Watkins的相应命题:如果k正则点可迁图G不是k连通的,那么G有一个因子,它的每一个分支都同构于同一个点可迁图.     

一类Y~(SG)(γλ,n)∪βS_n~G形图簇的伴随分解及其补图的色等价性

设G是m阶连同图,我们用S_n~G(n=km+1)表示把kG的每个分支的d_i度点分别与星图S_k+1的k个1度点重迭后得到的图,Y~(SG)(r_1n,n)表示把r_1S_n~G中每个分支的k度点依次与图的k度点邻接后得到的图,Y~(SG)(r_2λ_1,n)表示把τ_2Y~(SG)(τ_1n,n)中每个分支的r_1+k度点依次与图S_n~G的k度点邻接后得到的图,若k≥3,用Y~(sG)(r_kλ__(k-1),n)表示把τ_kY~(sG)(r_(k-1)λ_(k-2),n)中每个分支的τ_(k-1)+k度顶点依次与图S_n~G的k度点邻接后得到的图,这里λ_k=r_kλ_(k-1)+n.运用图的伴随多项式的性质,证明了一类新的图簇Y~(sG)(r_kλ__(k-1),n)∪β_kS_n~G的伴随多项式的因式分解定理,进而得到了这类图的补图的色等价图.