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

一个最小可行图的判定条件

设有n个集合X_1,…,X_n,一个以X=U_(i=1)~nX_i为顶点集的图G称为是一个关于(X_1,…,X_n)的可行图,如果对每一个X_i(i=1,…,n),导出子图G_i=G[Xi]是连通的。关于集合序列(X_1,…,X_n),含最少边数的可行图称为是最小可行图。本文证明,关于(X_1,X_2,X_3)的可行图G=G_1∪G_2∪G_3是最小可行图的充分必要条件是:当X_i∩X_j∩X_k≠φ(i,j,k)=1,2,3)时,G_i∩G_j∩G_k是树。它发展了由D.-Z.Du(堵丁柱)在1986年得到的一个结果。     

Kronecker乘积图的超连通性(英文)

设G1和G2是两个连通图,则G1和G2的Kronecker积G1×G2定义如下:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)}.我们证明了G×Kn(n≥4)超连通图当且仅当κ(G)n>δ(G)(n 1),其中G是任意的连通图,Kn是n阶完全图.进一步我们证明了对任意阶至少为3的连通图G,如果κ(G)=δ(G),则G×Kn(n≥3)超连通图.这个结果加强了郭利涛等人的结果.     

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

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

几类图的拉普拉斯特征值的前三项和的上界

设G是一个顶点集为V(G),边集为E(G))的简单图.S_k(G)表示图G的拉普拉斯特征值的前k项部分和.Brouwer et al.给出如下猜想:S_k(G)≤e(G)+((k+1)/2),1≤k≤n.证明了当k=3时,对边数不少于n~2/4-n/4的图及有完美匹配或有6-匹配的图,猜想是正确的.     

n=3pr情形的乘子猜想的解决

完善了1992年以来提出的研究乘子猜想的特征标方法,从而对n=3n1情形的乘子猜想取得了较大的进展.概略地说,证明了:在n=3n1的情形,用(n1,λ)=1代替n1＞λ,第二乘子定理仍然成立.进而证明了:在n=3pr的情形,把p＞λ的条件去掉,第一乘子定理仍然成立.即,设D是abel群G的一个(v,k,λ)-差集,n=3pr,p是素数,且(p,v)=1,则p是D的数值乘子.     

Jackson正则图定理的一个注记

§1.引言关于简单图上简单圈的研究,最近 Jackson 在[2]中证明了一个相当好的定理:任何一个δ正则的2-连通图 G,如果其顶点个数 n 满足n≤3δ,则 G 中存在一个 Hamilton圈。Jackson 在文章中还提到他相信在δ≥4时把 n 的限制放宽到 n≤3δ+1 是可能的。要证实他的这种看法是否成立,只须对 n=3δ+1 时来证明就行了。     

Chartrand问题的若干拓广

记 Ω(G)和π(G)分别为图 G 的全体支撑树和全体悬挂点所成之集.对于子集 S(?)V(G),定义Ω~(S)(G)(?){T∈Ω(G)|π(T)(?)S}.若 G 是赋权图,记Ω_min~(S)(G)为 Ω~(s)(G)中全体最小支撑树所成之集.Chartrand 猜想:若有 T_1,T_2∈Ω(G),其相应的悬挂点数分别为m 和 n,且 m相似文献   

无爪3 -正则图的独立数

如果图G的一个集合X中任两个点不相邻, 则称 X 为独立集合. 如果 N[X]=V(G), 则称X是一个控制集合. i(G)(β(G))分别表示所有极大独立集合的最小(最大)基数. γ(G)(Γ(G))表示所有极小控制集合的最小(最大)基数. 在这篇论文中, 作者证明如下结论: (1) 如果 G ∈R 且G 是n阶3 -正则图, 则 γ(G)= i(G), β(G)=n/3. (2) 每个n阶连通无爪3 -正则图 G, 如果 G(G≠ K₄) 且不含诱导子图K₄-e, 则 β(G) =n/3.     

K2Q的某些有限阶元素

本文证明了若n≥2,则G2n3m(Q)是K2Q的子群当且仅当n=2,m=0,并且通过改进[1]的方法,还证明了G25(Q),G49(Q)和G27(Q)都不是K2Q的子群,从而部分地证实了Browkin的一个著名猜想.     

RECENT PROGRESS ON SPHERICAL HARMONIC APPROXIMATION MADE BY BNU RESEARCH GROUP ——In memory of Professor Sun Yongsheng

As early as in 1990, Professor Sun Yongsheng, suggested his students at Beijing Normal University to consider research problems on the unit sphere. Under his guidance and encouragement his students started the research on spherical harmonic analysis and approximation. In this paper, we incompletely introduce the main achievements in this area obtained by our group and relative researchers during recent 5 years （2001-2005）. The main topics are： convergence of Cesaro summability, a.e. and strong summability of Fourier-Laplace series; smoothness and K-functionals; Kolmogorov and linear widths.     

Instructions for Authors

<正>Submission Authors must use LaTeX for typewriting,and visit our website www.actamath.com to submit your paper.Our address is Editorial Office of Acta Mathematica Sinica,Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,P.R.China.     

THE 8~(th) INTERNATIONAL CONGRESS ON INDUSTRIAL AND APPLIED MATHEMATICS

正August 10-14,2015Beijin,China The International Congress on Industrial and Applied Mathematics(ICIAM)is the premier international congress in the field of applied mathematics held every four years under the auspices of the International Council for Industrial and Applied Mathematics.From August 10 to 14,2015,mathematicians,scientists     

Boundedness for commutators of multipliers on Hardy type spaces

In this paper, we study the commutators generalized by multipliers and a BMO function. Under some assumptions, we establish its boundedness properties from certain atomic Hardy space Hb^p（R^n） into the Lebesgue space L^p with p 〈 1.     

A unified approach to certain problems of best local approximation

In this paper we study best local quasi-rational approximation and best local approximation from finite dimensional subspaces of vectorial functions of several variables. Our approach extends and unifies several problems concerning best local multi-point approximation in different norms.     

Towards Excellence in Science Chinese Academy of Sciences

<正>May 26,2014,Beijing Science is a human enterprise in the pursuit of knowledge.The scientific revolution that occurred in the 17th Century initiated the advances of modern science.The scientific knowledge system created by     

THE 8~(th) INTERNATIONAL CONGRESS ON INDUSTRIAL AND APPLIED MATHEMATICS

<正>August 10-14,2015Beijing,ChinaThe International Congress on Industrial and Applied Mathematics(ICIAM)is the premier international congress in the field of applied mathematics held every four years under the auspices of the International Council for Industrial and Applied Mathematics.From August 10 to 14,2015,mathematicians,scientists     

Bounds for the zeros of polynomials

Let P(z)=∑↓j=0↑n ajx^j be a polynomial of degree n. In this paper we prove a more general result which interalia improves upon the bounds of a class of polynomials. We also prove a result which includes some extensions and generalizations of Enestrǒm-Kakeya theorem.