完全四部图的色性

设G是一个图，P(G，λ)是G的色多项式．若P(G，λ)=P(H，λ)，则称G和H是色等价的，简单地用G～H表示．令[G]={H\H～G)．若[G]={G)，称G是色唯一的．用G=K(n1，n2，n3，n4)表示完全四部图且2≤n1≤n2≤n3≤n4，得到了[G]С{K(x，y，z，w)-S｜z y w =n1 n2 n3 n4,1≤z≤y≤z≤w≤n4-1，或1≤x≤y≤z≤n3-1和w=n4U{G}，其中S是K(x，y，z，w)的某s条边组成的集合且K(x，y，z，w)-s表示从K(x，y，z，w)中删去S中所有边得到的图．从而证明了当n≥k 2，t≥2时，K(n-k，n，n，n)是色唯一的．     

书图和扇形图的Ramsey数

对给定的两个图G和H,Ramsey数R(G,H)是最小的正整数N,使得对完全图KN的边任意红/蓝着色,或者存在红色子图G,或者存在蓝色子图H.用G+H表示两个不交的图G和H之间完全连边所得到的图.设Bm=K2+mK1,Fn=K1+nK2.证明了当m≥1且n≥max{2,3 m-2},R(Bm,Fn)=4n+1;当n≥38,R(F2,K2,n)=2n+3.     

结合图的导出匹配可扩性

简单图G和H的结合图G[H]的顶点集为V(G)×V(H),其中(u,v)和(u′,v′)相邻的充分必要条件是:或者uu′∈E(G)或者u＝u′并且vv′∈E(H).研究了结合图G[H]的导出匹配可扩性,证明了若G和H是非平凡图,G是连通图,且G和H满足下列条件之一,则G[H]是导出匹配可扩的:(1) G和H中有一个是导出匹配可扩的;(2) G和H都有完美匹配;(3) G和H中一个有完美匹配,另一个有几乎完美匹配.     

关于完全三部图色唯一性的判定

G是简单图,用P(G,λ)表示图的色多项式.若对任意简单图H当P(H,λ)=P(G,λ)时,都有HG,则称G是色唯一图.Liu R.,Zhao H. X.和Ye C.已经证明:当n和k为整数且满足n≥k 2≥4,完全三部图K(n-k,n,n)是色唯一的;当n和k满足n≥2k≥4时,完全三部图K(n-k,n-1,n)是色唯一的.在本文中,证明了当k是奇数且n≥k2/4 15/4≥6,或k是偶数且n≥k2/4 4≥5时,完全三部图K(n-k,n-2,n)是色唯一的;当k是奇数且n≥k2/4 19/4≥7,或k是偶数且n≥k2/4 5≥9时,K(n-k,n-3,n)是色唯一的.     

恰有2个内度的2维Torus网络的定向图

设G是一个简单图且D是G的一个定向图.若对D中任意顶点x,d-(x)=a或b,则称G是[a,b]可实现的.主要研究了2维Torus网络中[a,b]可实现的充要条件.设H=Torus(p,k)是一个2维Torus网络,其中p和k是2个不小于3且奇偶性相同的正整数.设0≤a,b≤4,则H是[a,b]可实现的当且仅当存在非负整数s和t使得s+t=kp且as+bt=2kp.     

图的强直积的2-距离染色(英文)

设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。     

△(G)≥6的Halin图的点强全染色

图G(V，E)的正常k-全染色σ称为G(V，E)的k-点强全染色当且仅当A↓v∈V(G)，N[v]的元素染不同色，其中N[v]={uluv∈EG)}∪{v}，xT^vs(G)=min{k|存在G的k-点强全染色}称为G(V，E)的点强全色数。本文证明了：对于△(G)≥6的Halin图G(V，E)，有xT^vs(G)≤△(G) 2，其△(G)表示图G的最大度。     

完全多部图中的色正规图类

设G是简单图,用P(G,λ)表示图G的色多项式。简单图H称为与G是色等价的(记作H∽G),如果P(H,λ)=P(G,λ)。简单图类L称为色正规图类,若对任意H,G∈L使H∽G,都有H与G同构(记作H≌G)。本文证明完全三部图类和完全四部图类是色正规图类。     

关于团图的一个注记

在这个注记中,我们将[1]定理3·1改进成:图G满足条件2~(|G|-ω(G))=|K(G)|当且仅当G是Turan图T(|G|,ω(G))的子图且同时G包含一个子图同构于[1]定理2·3的证明中引入的Hedman图H(|G|,ω(G))。我们还指出[1]定理3·2是错误的。事实上我们进一步证明了:如果图G满足条件2~(|G|-ω(G))=|K(G)|,则或者K(G)是Neumann图或者K(G)是完全图,并且K(G)为完全图当且仅当Δ(G)=|G|-1。     

关于二分图的正交因子分解

设 G是二分图 ,fi,gi 是定义在图 G的顶点集 V( G)上的非负整数函数且 gi( x)≤ fi( x) , x∈ V( G) ,1≤ i≤ m。若二分图 G的边能划分成 m个边不交的 [g1,f1]-因子 F1,… [gm,fm]-因子Fm,则称 F={F1,… Fm}是二分图 G的一个 [gi,fi]m1-因子分解 ,又若 H是二分图 G的一个有 m条边的子图 ,若对任意的 1≤ i≤ m有 | E( H)∩ E( Fi) | =1 ,则称 F与 H是正交的。主要研究二分图的正交[gi,fi]m1-因子分解并给出一个结果。     

舵轮图都是强协调图

一个有e条边的简单图G称为是强协调的,若有V(G)到{0,1,…,e-1}的单射h,使导出映射h~*:h~*(uv)=h(u)+h(v)是由E(G)到{1,2,…,e}的一个双射。舵轮图H_n是由含n个顶点的圈C_n内添加一个与C_n的每个顶点都相邻的顶点,且再在C_n的每个顶点上都添上一条悬挂边而得到的图。本文中证明了,所有舵轮图都是强协调图,因而回答了[2]中一个open问题。     

关于图的k-因子的一个新结果

图G的一个-k正则生成子图称为G的一个-k因子。文章首先给出了一个图G有-k因子的一个充分条件,即若G是简单图,v是偶数且)2(2/)(-+kvGd(这里k是整数且3k),则G有-k因子。从而推广了文献[1]的一个结果。并得到了一个相关的结果。     

关于完全三部图K(n-k,n,n+k)的色性

设Ｇ为简单图,Ｐ（Ｇ,λ）的色多项式,若对任意简单图Ｈ满足Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）,都有Ｈ与Ｇ同构,则称Ｇ是色唯一图,设Ｋ（ｍ,ｎ,ｒ）表示完全三部图,证明了：（１）对任意非负整数ｋ,若ｎ≥２√－３ｋ／３＋ｋ＾２,则Ｋ（ｎ－ｋ,ｎ,ｎ＋ｋ）是色唯一图。（２）若ｎ≥９,则Ｋ（ｎ－３,ｎ,ｎ＋３）是色唯一图。     

边-超欧拉图的一个度数和条件

图G称为边-超欧拉图,如果对于它的任一条边e,都有欧拉生成子图H包含e．给出了边-超欧拉图的一个度数和条件,即：设G是2一边连通的n个顶点的简单图,如果n≥100并且对于图G的任意两个不相邻的顶点u和v都有d（u）＋d（v）≥2/5n,那么对于图G的任意一条边e,或者G有欧拉生成子图H包含e,或者G（G关于e的剖分图）可以被收缩成K2.3或K2.5．     

关于连通图端片的一些结果

设G=(V，E)为简单连通图，A包括V．G[A]称为G的断片，如果存在极小割S，使得G[A]是G—S的分支．G[A]称为G的端片，如果G[A]为G的断片，且对A的任何真子集B，G[B]不是G的断片．给出G的端片的一些性质，得到端片个数∑≤|V|的结论，并给出等号成立的一些必要条件及充分条件．     

1-可扩偶图的刻划

设G是一个具有二分类(X，Y)的偶图且M是G的一个完美对集。文章证明：G是1—可扩图当且仅当G有如下耳朵分解G=e P1 P2 … Pr使得e∈M并且每个只是起始和终止边都在E(G)＼M中的M-交错路。文章还给出一个有效算法判定一个偶图是否1—可扩图并找出该图的耳朵分解。     

阶数不小于6的强-[s，t]图的泛圈性

一个图G为强-[s,t]图,如果G中任意s个顶点的集合S的导出子图中至少含有t条独立边,本文证明了阶数≥6的强-[4,2]图是泛圈的。     

二部图K(m,n)-A中的色正规图类

设Ｐ（Ｇ,λ）表示简单图Ｇ的色多项式。简单图Ｈ称为与Ｇ是色等价的（记作Ｈ￣Ｇ）,如果Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）。简单图类Ｌ称为色正规图类,若对任意Ｈ,Ｇ∈Ｌ使Ｈ￣Ｇ都有Ｈ与Ｇ同构。