二分（0，mf—m＋1）-图的正交（0，f）-因子分解

设G=（X,Y,E（G））是一个二分图,分别用V（G）=X∪Y和E（G）表示G的顶点集和边集．设f是定义在V（G）上的整数值函数且对任意x∈V（G）有f（x）≥k．设H1,H2,…,Hk是G的k个顶点不相交的子图,且｜E（Hi）｜=m,1≤i≤k．本文证明了每个二分（0,mf—m＋1）．图G有一个（0,f）-因子分解正交于Hi（i=1,2,…,k）     

图Gn的优美表示

将给出三个结果：（i）如果图G是SZ（｜S｜=n≥2）上的整数和图,那么0∈S当且仅当图G至少有一个（n-1）度顶点;（ii）图G（G≠K2）是至少有两个零点的整数和图当且仅当G■K2·Gn;（iii）设图G（G≠K2）是SZ上的整数和图,｜S｜=n＋2,n∈N＋.若图G至少有两个零点,则S={mx｜m=-1,0,1,2,…,n;x∈Z且x≠0}.     

汉米尔顿图泛圈性的奥尔型条件

本文所说的图是简单图,未定义的术语见[1,2].n 阶图 G,n≥3,若有长为 n 的圈,则说 G 是汉米尔顿图;若对每个 k,3≤k≤n,G 含有长为 k 的圈,则说 G 是泛圈图.定理1.在 n 阶图 G 中,若对任何点对 x,y∈V(G),xy(?)E(G),都有 d(x)+d(y)≥n,则 G 是汉米尔顿图.     

图中相互独立的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的路，使得所有这些圈和路都是相互独立的，并且此度条件是最好的.     

无爪图的次与Hamilton连通性

本文证明了：设G是n阶、k（≥3）连通无爪图，且不含同构于B的导出子图，若存在点v_0∈V（G），使d（v_0）≥n-2k＋4，则G是Hamilton连通的．     

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

图中具有推广的正交（g，f）-因子分解的子图

设G是一个图，具有顶点集V（G）和边集E（G）．设g和f是定义在V（G）上的整数值函数且对每个x∈y（G）有g（x）≤f（x）．本文证明了如下的结果：若G是一个（mg＋kr，mf-kr）一图，且对每个x∈V（G）有g（x）≥r-1，H和G的任意给定的有kr条边的子图，则G中含有一个子图R，使R有（g，f）-因子分解r-正交于H，其中m，k和r是正整数且k〈m.     

关于图是(r,n)-临界图的一个邻域条件

设n，m和r是满足r≥2，n≥0，m≥3的整数，且当r是奇数时，假设r≥m-1．称一个图为K1,m-free，如果它不包含以Kt,m为导出的子图．称一个图G为一个（r,n）-临界图，如果在删去G的任意n个点后，剩下G的子图都有一个r-因子,设G是一个Kl,m-free的（n＋1）-连通图，且阶为｜G｜以及r（｜G｜≥n）是偶数,证明了：如果G的最小度至少是r＋n＋m-1，阶｜G｜≥8r5＋n，并且对V（G）的任意独立点集{x1，x2}都有｜NG（x1）∪NG（x2）｜≥（｜G｜＋n）／2，那么G是一个（r,n）-临界图．关于G的最小度和｜NG（x1）∪NG（X2）｜的下界是紧的。     

泛连通图定理和Ore2条件

记Ore2=min{d(y) d(x)|x,y∈V(G),d(x,y)=2}，本得到：若n阶图G的Ore2≥n 1，则G是[5;n]泛连通图。此是比Faudree等人的定理进一步的结果。     

与星正交的[0,k_j]~m_1-因子分解

设G是一个图，k1；k2，…，km是正整数，如果对所有的x∈V（G）有0≤dG（x）≤k1＋k2＋…＋km－m＋1成立，K是G的m-星，则G有一个［0，kj］1m-因子分解与K正交．     

图的上可嵌入性与圈中顶点度

本文利用非上可嵌入图的充要条件,结合圈中顶点最大度与图的上可嵌入性之间的关系,得到了下两个结果:(1)设G是2-边连通简单图,若对G中任意圈G,存在点x∈C满足,d(x)>|V(G)|/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.(2)设G={x,y;E}为简单二都图,且是2-边连通的. |x|=m,|Y|=n(m,n≥3),若对G中任意圈C,存在点x∈C且x∈X满足d(x)>n/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.     

带弦圈的最小2宽直径

设k为正整数,G是简单k连通图.图G的k宽直径,dk(G),是指最小的整数ι使得对任意两不同顶点x,y∈V(G),都存在k条长至多为ι的内部不交的连接x和y的路.用C(n,t)表示在圈Gn上增加t条边所得的图.定义h(n,t):min{d2(C(n,t))}.本文给出了h(n,2)=[n/2].而且,给出了当t较大时h(n,t)的界.     

Hamilton连通性和邻域并条件

设G＝（V，E）为简单图，δ为图G的最小度，1987年Faudree等人给出NC＝min{|N(x)∪N(y)‖x,y∈V(G),xy∈N(G)}，有关文献曾研究3连通的H连通图，本文进一步得到：若G是n阶2连通图，且NC≥n-δ，则G除几个图外均是H连通图，从而，完成了邻并条件的H连通图问题。     

Bondy的泛圈图定理的改进

记G=(V,E)是简单图,1971年Bondy得到O re条件下的泛圈图的著名结果:若2连通n阶图G的不相邻的任两点x、y均有d(x) d(y)≥n,则G是泛圈图或G=Kn/2,n/2.这里进一步研究条件d(x) d(y)≥n-1,得到:若2连通n阶图G的不相邻的任两点x、y均有d(x) d(y)≥n-1,则G是泛圈图或G∈{K(Cn 1)/2∨G(n-1)/2,Kn/2,n/2}.本文作者得知最近国际著名权威专家Ho lton等人也得到完全相同的结果,但本证明更简捷.     

K3-free图的线图的哈密顿性

设G是一个简单图，Gi G，G1在G中的度定义为d（Gt）=∑v∈v（c）d（v），其中d（v）为v在G中的度数。本文的主要结果是：设G是n≥2阶几乎无桥的简单连通K3-free图，且G≌k1,n-1、Q1和Q2，若对G中任何同构于四个顶点路的导出子图I有d（I）≥n＋2，则G有一个D-闭迹，从而G的线图L（G）是哈密顿图。     

均衡二部图中点不交的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(2,1)标号问题

图G的L( 2 ,1 )标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1 ,则｜f(x) -f(y) ｜≥ 2 ;若d(x ,y) =2 ,则｜f(x) -f(y) ｜≥ 1 .图G的L( 2 ,1 ) 标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) ≤Δ2 .本文给出了Kneser图 ,Mycieklski图 ,Descartes图 ,Halin图的λ值的上界 ,并证明了上述猜想对以上几类图成立     

任意长圈覆盖指定的独立的点

An invariant σ2（G） of a graph is defined as follows： σ2（G） ：= min{d（u） ＋ d（v）｜u, v ∈V（G）,uv ∈ E（G）,u ≠ v} is the minimum degree sum of nonadjacent vertices （when G is a complete graph, we define σ2（G） = ∞）. Let k, s be integers with k ≥ 2 and s ≥ 4, G be a graph of order n sufficiently large compared with s and k. We show that if σ2（G） ≥ n ＋ k- 1, then for any set of k independent vertices v1,..., vk, G has k vertex-disjoint cycles C1,..., Ck such that ｜Ci｜ ≤ s and vi ∈ V（Ci） for all 1 ≤ i ≤ k.
The condition of degree sum σs（G） ≥ n ＋ k - 1 is sharp.     

关于图的距离标号问题

图G的L（2，1）-标号是一个从顶点V（G）集到非负整数集的函数f（x），使得若d（x，y）：1，则｜f（x）-f（y）｜≥2；若d（x，y）=2，则｜f（x）-f（y）｜≥1。图G的L（2，1）-标号数A（G）是使得G有max{f（v）：v∈V（G）}=k的L（2，1）-标号中的最小数愚。本文将L（2，1）-标号问题推广到更一般的情形即L（d1，d2，d3）-标号问题，并得出了复合图的λd1，d2，d3（G）的上界。     

关于两类平面图及相关图的L(d1,d2)-标号问题

图G的L(2,1)标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥(2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)标号数λ(G)是使得G有max{f(v)V∈V(G)}=k的L(2,1)标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.本文将L(2,1)-标号推广到L(d1,d2)-标号,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d1,d2)-标号的上界,作为推论,本文证明了对上述几类图,有上述猜想成立.