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

Biased Partitions and Judicious k-Partitions of Graphs

Let G =(V, E) be a graph with m edges. For reals p ∈ [0, 1] and q = 1-p, let m_p(G) be the minimum of qe(V_1) + pe(V_2) over partitions V = V_1 ∪ V_2, where e(V_i) denotes the number of edges spanned by V_i. We show that if m_p(G) = pqm-δ, then there exists a bipartition V_1, V_2 of G such that e(V_1) ≤ p~2m-δ + p(m/2)~(-1/2)+ o(√m) and e(V_2) ≤ q~2m-δ + q(m/2)~(-1/2) + o(√m) for δ = o(m~(2/3)). This is sharp for com_plete graphs up to the error term o(√m). For an integer k ≥ 2, let fk(G) denote the maximum number of edges in a k-partite subgraph of G. We prove that if fk(G) =(1-1/k)m + α,then G admits a k-partition such that each vertex class spans at most m/k~2-Ω(m/k~(7.5)) edges forα = Ω(m/k~6). Both of the above im_prove the results of Bollob′as and Scott.     

最大度与最小度相差不超过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.     

一致超图中Berge线性森林的Turán数

设F是一个图,■是一个超图,如果存在一个双射φ:E(F)→E(■),使得?e∈E(F)有e?φ(e),那么称超图■是Berge-F.不含Berge-F作为子超图的n阶r-一致超图所能达到的最大边数称为Berge-F的Turán数,记作ex_r(n,Berge-F).线性森林是指连通分支全是路或者孤立顶点的图.设■_n,k是一类含有n个顶点k条边的线性森林图族.本文研究了r-一致超图中Berge-■_n,k的Turán数.当r≥k+1和3≤r≤■(k-1)/2■-1时,分别确定了ex_r(n,Berge-■_n,k)的精确值;当■(k-1)/2■≤r≤k时,给出了ex_r(n,Berge-■_n,k)的上界.     

不含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)-可染的.     

关于补差集与Hadamard矩阵

本文着重讨论了H型补差集,主要结果是: (1) 证明了存在2~i·10~j 18~k·26~r·50~s·82~t阶H型2-补差集;其中i,j,k,r,s,t,为任意非负整数; (2) 给出了71阶和73的H型4-补差集; (3) 定义了v阶Abel群上的C划分, 给出了v=37和61时的C划分,指出了v∈S=S_2∪S_1∪S_3时存在C划分,其中 S_1={2k+1:O≤k≤16}∪{59} S_2={2~i·lO~j·26~k+1:i, j, k为任意非负整数}, S_3={37,61}: (4) 指出了当v′∈S,u∈W=W_1∪W_2∪W_3时,存在v′v阶H型4-补差集,其中 W_1={3~n:n≥1}, W_2={2k+1:0≤k≤14}∪{37,43}, W_3={n:2n-1≡1(mod4)是一素数的方幂}; (5) 利用C划分和[3]的一个结果证明了,当m∈S,n∈W_3时,存在2mn~r(n+1)阶H阵(r≥O); (6) 最后还证明,当在同一个u≡3(mod4)阶Abel群上存在{u;k;λz}差集和{u;1/2(u-1);1/4(u-3)}差集时,且存在v+l=u+1-4(k-λ)阶skew type H阵,则存在uv~r(v+1)阶H阵(r≥O).     

A bound on judicious bipartitions of directed graphs

Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously,which have received much attention lately.Scott(2005)asked the following natural question:What is the maximum constant cdsuch that every directed graph D with m arcs and minimum outdegree d admits a bipartition V(D)=V_1∪V_2 satisfying min{e(V_1,V_2),e(V_2,V_1)}cdm?Here,for i=1,2,e(V_i,V_3-i)denotes the number of arcs in D from V_i to V_3-i.Lee et al.(2016)conjectured that every directed graph D with m arcs and minimum outdegree at least d 2 admits a bipartition V(D)=V_1∪V_2 such that min{e(V_1,V_2),e(V_2,V_1)}≥((d-1)/(2(2 d-1))+o(1))m.In this paper,we show that this conjecture holds under the additional natural condition that the minimum indegree is also at least d.     

不含4-圈和9-圈的平面图是(2,0,0)-可染的

设d_1,d_2,...d_k为尼个非负整数.若图G的顶点集V可划分成k个子集合V_1,V_2…,V_k,使得对于任意的i∈{1,2,...,k},由V_i导出的子图G[V_i]的最大度至多为d_i,则称图G是(d_1,d_2,...,d_k)-可染的.1976年,Steinberg猜想:不含4-圈和5-圈的平面图是(0,0,0)-可染的.在Steinberg猜想的驱动下,人们证明了以下三个结论:(1)对每一个i∈{5,6,7,8,9},不含4-圈和i-圈的平面图是列表(1,1,1)-可染的;(2)对每一个i∈{5,6,7,8,9},不含4-圈和i-圈的平面图是(1,1,0)-可染的;(3)对每一个i∈{5,6,7,8},不含4-圈和i-圈的平面图是(2,0,0)-可染的.为使结论(3)更加完整,本文证明不含4-圈和9-圈的平面图是(2,0,0)-可染的.     

套链分解

Let X1,X2,...,Xk be k disjoint subsets of S with the same cardinality m.Define H(m,k) = {X (C) S: X (C) Xi for 1 ≤I ≤k} and P(m,k) = {X (C) S : X ∩ Xi ≠φ for at least two Xi's}.Suppose S = Uki=1 Xi,and let Q(m,k,2) be the collection of all subsets K of S satisfying|K ∩ Xi|≥ 2 for some 1 ≤ I ≤ k.For any two disjoint subsets Y1 and Y2 of S,we define F1,j = {X (C) S : either |X ∩ Y1|≥ 1 or |X ∩ Y2|≥ j}.It is obvious that the four posers are graded posets ordered by inclusion.In this paper we will prove that the four posets are nested chain orders.     

一个素变量丢番图问题

设k和r是满足k≥3及r≥Ψ(k)+1的正整数,这里当3≤k≤4时,Ψ(k)=2~(k-1);而当k≥5时,Ψ(k)=1/2k(k+1).假定δ和ε是给定的足够小的正数,λ_1,λ_2,…,λ_(r+1)是不全同号且两两之比不全为有理数的非零实数.对于任意实数η与0σ2~(1-2k)/r-1,证明了:存在一个正数序列X→+∞,使得不等式|λ_1p_1~k+λ_2p_2~k+···+λ_rp_r~k+λ_(r+1)p_(r+1)+η|(max(1≤j≤r+1)p_j)~(-σ)有》■X~(■-(2~(1-2k))/(r-1)+ε组素数解(p_1,p_2,…,p_(r+1)),这里(δX)~(1/k)≤p_j≤X~(1/k)(1≤j≤r)及δX≤p_(r+1)≤X.这改进了之前的结果.     

P_n~k的均匀全染色

设G(V,E)是一个简单图,f是G的一个k-正常全染色,若f满足||Vi∪Ei|-|Vj∪Ej||≤1(i≠j),其中Vi∪Ei={v|f(v)=i}∪{e|f(e)=i},则称f为G的k-均匀全染色,简记为k-ETC.并称eχT(G)=min{k|G存在k-均匀全染色}为G的均匀全染色数.本文将通过很好的全染色方法得到eχT(Pkn)=5(n≥2k+1),并证明了对Pkn,[5]中猜想是正确的.     

星样树与路的笛卡尔积图的任意可分性（英文）

一个图G称为是任意可分的(简记AP),如果对于正整数|V(G)|的任一满足∑_(i=1)~pn_i=|V(G)|的划分τ=(n_1,n_2,…,n_p),总是存在顶点集V的一个划分(V_1,V_2,…,V_p)满足|V_i|=n_i,i=1,2,…,p,使得每个V_i导出的图是图G的一个连通子图.记S(a_1,a_2,…,a_t,b_1,b_2,…,b_l)是最大度△(S)=t+l的星样树,其中a_i是奇数,b_j是偶数且a_1≤a_2≤…≤a_t,b_1≤b_2≤…≤b_l.我们证明了对于一个大于等于2的偶数n,当△(S)≤n+1时,如果t≤2,或t≥3且a_3 1,则笛卡尔积图S□P_n是AP的.对于一个大于2的奇数n,如果△(S)≤n+1且t≤2,则S□P_n是AP的;如果△(S)≤n+1且t≥3,则S□P_n不是AP的.     

带有限位势的非线性Schrdinger方程组的无穷多变号解

本文考虑非线性Schrdinger方程组-?u j+λj(x)u j=k i=1β_(ij) u_i~2 u_j,x∈R~N,u_j(x)→0,当|x|→∞时,j=1,...,k,其中N=2,3,β_(ij)是常数,满足β_(jj)0(j=1,...,k),β_(ij)=β_(ji)0(1≤ij≤k),λ_j(j=1,...,k)是位势函数.首先考虑带强制位势的方程组,利用流不变集方法证明带强制位势的方程组有无穷多变号解;然后在位势λ_j具有一定渐近性质(见正文(V_1)–(V_4))时,通过集中紧性分析,证明带强制位势扰动方程组的解趋于原来有限位势的方程组的解,从而证明原方程组有无穷多变号解.     

Almost Everywhere Convergence of Sequences of Cesàro and Riesz Means of Integrable Functions with Respect to the Multidimensional Walsh System

The aim of this paper is to prove the a.e.convergence of sequences of the Cesa`ro and Riesz means of the Walsh–Fourier series of d variable integrable functions.That is,let a=(a1,...,ad):N→Nd(d∈P)such that aj(n+1)≥δsupk≤n aj(k)(j=1,...,d,n∈N)for someδ0 and a1(+∞)=···=ad(+∞)=+∞.Then,for each integrable function f∈L1(Id),we have the a.e.relation for the Ces`aro means limn→∞σαa(n)f=f and for the Riesz means limn→∞σα,γa(n)f=f for any 0αj≤1≤γj(j=1,...,d).A straightforward consequence of our result is the so-called cone restricted a.e.convergence of the multidimensional Ces`aro and Riesz means of integrable functions,which was proved earlier by Weisz.     

On All Fractional （a,b, k）-Critical Graphs

Let a,b,k,r be nonnegative integers with 1≤a≤b and r≥2.LetG be a graph of order n with n(a+b)(r(a+b)-2)+ak/a.In this paper,we first show a characterization for all fractional(a,b,k)-critical graphs.Then using the result,we prove that G is all fractional(a,b,k)-critical if δ(G)≥(r-1)b2/a+k and |NG(x1)∪NG(x2)∪···∪NG(xr)|≥bn+ak/a+b for any independent subset {x1,x2,...,xr} in G.Furthermore,it is shown that the lower bound on the condition|NG(x1)∪NG(x2)∪···∪NG(xr)|≥bn+ak/a+b is best possible in some sense,and it is an extension of Lu's previous result.     

Pkn的均匀全染色

设G(V,E)是一个简单图,f是G的一个k-正常全染色,若f满足||Vi∪Ei|-|Vj∪Ej||≤1(i≠j),其中Vi∪Ei={v|f(v)=i}∪{e|f(e)=i},则称f为G的k-均匀全染色,简记为k-ETC.并称χeT(G)=min{k|G存在k-均匀全染色}为G的均匀全染色数.本文将通过很好的全染色方法得到χeT(Pkn)=5(n≥2k 1),并证明了对Pkn,[5]中猜想是正确的.     

单圈图的最大特征值的上界的改进

Let G（V, E） be a unicyclic graph, Cm be a cycle of length m and Cm G, and ui ∈ V（Cm）. The G - E（Cm） are m trees, denoted by Ti, i = 1, 2,..., m. For i = 1, 2,..., m, let eui be the excentricity of ui in Ti and ec = max{eui ： i = 1, 2 , m}. Let κ = ec＋1. Forj = 1,2,...,k- 1, let δij = max{dv ： dist（v, ui） = j,v ∈ Ti}, δj = max{δij ： i = 1, 2,..., m}, δ0 = max{dui ： ui ∈ V（Cm）}. Then λ1（G）≤max{max 2≤j≤k-2 （√δj-1-1＋√δj-1）,2＋√δ0-2,√δ0-2＋√δ1-1}. If G ≌ Cn, then the equality holds, where λ1 （G） is the largest eigenvalue of the adjacency matrix of G.     

On the Equation n_1n_2= n_3n_4 Restricted to Factor Closed Sets

We study the number of solutions N(B,F) of the diophantine equation n_1n_2 = n_3 n_4,where 1 ≤ n_1 ≤ B,1 ≤ n_3 ≤ B,n_2,n_4 ∈ F and F[1,B] is a factor closed set.We study more particularly the case when F={m = p_1~(ε1)···p_k~(εk),ε_j∈{0,1},1 ≤ j ≤ k},p_1,...,p_k being distinct prime numbers.     

高维空间的一个Heilbronn型问题

本文研究了以下Heilbronn型问题:设S是欧氏空间按R~k 中由有限个点A_1,A_2,…,A_n组成的集合,令d(S)=min{A_iA_j|1≤i相似文献