ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K1,8,n

The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph K_m,n (m≤ n) is Z(m,n), where Z(m,n)=\lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor\lfloor\frac{n}{2}\rfloor$\lfloor\frac{n-1}{2}\rfloor$ (for any real number x, $\lfloor x\rfloor$ denotes the maximal integer no more than x). Presently, Zarankiewicz' conjecture is proved true only for the case m≤ 6. In this article, the authors prove that if Zarankiewicz' conjecture holds for m≤9, then the crossing number of the complete tripartite graph K_1,8,n is $Z(9, n)+ 12\lfloor\frac{n}{2}\rfloor$.     

完全三部图K(n_1,n_2,n_3)的色唯一性

设G是简单图,用P(G,λ)表示图G的色多项式.若对任意简单图H使P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图.令K(n     

关于完全三部图K(m,n,r)的色唯一性

本文研究完全三部图K(m,n,r)的色唯一性问题，通过比较两个色等价图的色划分数的方法，得出两个关于K(m,n,r)为色唯一图的一般形式数值条件，基本上解决了K(m,n,r)为色唯一图的判定问题．     

关于图的符号控制数的下界

图的符号控制数的研究有许多应用背景，但图的符号控制数的计算是NP完全问题，因而确定其上下界有重大意义。本文在[5]的基础上，引进了新参数δ^*(G)，全面改进了[5]所给出的符号控制数的下界，并给出了一些可达下界的图。     

图G的邻强边色数的一个上界

本文给出了连通图G(V,E)(△(G)≥3)的邻强边色数的一个上界,证明了Xas(G)≤3△(G)-1.     

图K_n和K_(n,n)的7-匹配设计和简单设计(英)

本文结出图K_n和K_(n,n)的7-匹配设计的存在性和由两个简单的（n，k，λ）-设计（i＝1，2）构造简单的（n，k，λ＋λ_2）设计的条件．     

一类泛连通无爪图

本文证明了如果Ｇ是３连通无爪图，且Ｇ的每个导出子图Ａ，Ａ＋都满足（ａ１，ａ２），则Ｇ是泛连通图（除了当ｕ，ｖ∈Ｖ（Ｇ），ｄ（ｕ，ｖ）＝１时，Ｇ中可能不存在（ｕ，ｖ）－ｋ路外，这里２≤ｋ≤４）．     

K_(1,p)~k-FACTORIZATION OF COMPLETE BIPARTITE GRAPHS

§ 1　IntroductionLet Km,nbe a complete bipartite graph with two vertex sets having m and n vertices,respectively.A subgraph F of Km,n is called a spanning subgraph of Km,nif F contains allthe vertices of Km,n.Itis clearthata graph with no isolated vertices is uniquely determinedby the setofits edges.So in this paper,we considera graph with no isolated vertices to bea setof2 -elementsets ofits vertices.Letk be a positive integer.A K1 ,k-factor of Km,nis aspanning subgraph F of Km,nsuch th…     

树图边色数的界

本文研究树图的边色数，确定了其上界与下界，并进而考虑界的精确性。     

关于K_（1，r）－free图的连通因子

本文证明了每个连通的Ｋ１，ｒ－ｆｒｅｅ图Ｇ，如果有［ｆ，ｇ］－因子Ｆ，则它就有包含Ｆ的［ｆ，ｇ＋ｒ－１］连通因子．     

Petersen图的Hamilton性和边色数

对简单图G(V,E),定义图G的关联图I(G)为V(I(G))={(ve)|v∈V(G)且e∈E(G)和v与e关联},E(I(G))={(ue,vf)Iu=v或e=f或uv=e或uv=f}.本文证明了Petersen图可被分解为边不交的Hamilton-圈和一个1-因子的并.     

图K(r,2)的邻强边色数

本文给出了每部有2个点的完全r-部图(r≥2)的邻强边色数.     

关于U-统计量完全收敛性

本文讨论了满足E[f(xi,yj)xi]=E[f(xi,yj)xj]=0的U－统计量最大值完全收敛性的充分条件,降低了王岳宝1996年论文中的矩条件,进一步对一般形式的多元函数的U－统计量最大值的完全收敛性的充分条件进行了讨论,得到了较理想的结果。     

图的独立数的一个新下界

设α（Ｇ）表示简单图Ｇ＝（Ｖ，Ｅ）的独立数．本文给出了α（Ｇ）的一个新的下界：α（Ｇ）≥∑ｖ∈Ｖ（λｄ（ｖ）＋１）／（ｄ（ｖ）＋λｄ（ｖ）＋１），其中λｄ（ｖ）＝ｍａｘ｛０，βＮ（ｖ）－ｄ（ｖ）｝，ｄ（ｖ）＝｜Ｎ（ｖ）｜，Ｎ（ｖ）＝｛ｗ∈Ｖ｜（ｖ，ｗ）∈Ｅ｝，βＮ（ｖ）＝ｍｉｎｗ∈Ｎ（ｖ）ｄ（ｗ）．     

关于给定控制数的连通二部图的极大图的刻画

本文研究了给定控制数的连通二部图的极大图的结构问题.利用分类讨论思想和数学归纳法,刻画了控制数等于3和大于等于4这两类边数达到极值时的连通二部图.本文所得结果可用于进一步研究给定全控制数的连通二部图的极大图问题.     

完全三部图K(n-k,n,n)的色唯一性

通过对图的特征子图个数的比较,给出了图K(n-k,n,n)色唯一性的数值条件.     

轮图的广义Mycielski图的邻强边色数

设图 G(V,E)为简单图 ,V(Mn(G) ) |{ v0 1,v0 2 ,… ,v0 p;v11,v12 ,… ,v1p,… ,vn1,vn2 ,… ,vnp}E(Mn(G) ) =E(G)∪ { vijv(i+ 1) k|v0 jv0 k ∈ E(G) ,1≤ j,k≤ p ,i =0 ,1,… ,n - 1}称 Mn(G)为 G的 n广义 Mycielski图 ,n为自然数 .本文得到了轮的广义 Mycielski图的临强边色数 .     

关于图的L(2,1)标号核图

图的L(2,1)标号核图来自频率分配问题而导致的图论问题.在本文中,我们证得(i)对任意简单图G,存在G的一个标号核图Gcore,使得L(G)=L(Gcore)和L(G)≥|V(Gcore)|-1;(ii)设图G有p个顶点且边集|E(G)|≠φ,存在路 Pi G(1≤i≤m)和路Hs G(1≤s≤n),其中在G中V(Pi)∩V(Pj)=φ(i≠j),在G中V(P,)∩V(Pt)=φ(s≠t),则有m∑t=1|V(Pt)|+n∑s=1|V(Hs)|-(m+n)≥p;(iii)G是p(p≥5)个顶点的简单图,则有p+3≤L(G)+L(G)≤3p-4.     

连通无向图Rabin数的一个界

可靠性和有效性是互连网络设计的重要标准,而Rabin数是度量网络容错性和传输延迟的重要参数.将通过图的容错直径给出2- 连通无向图和~3- 连通无向图的~Rabin 数r_2(G)和r_3(G)的界;同时也得到r_2(G) = D_2(G)成立的一个条件.