变换图G++-的连通度

本文所研究的图G的变换图G++-是以V(G)∪E(G)作为顶点集的图,它的两个顶点u与v被一条边连接当且仅当下列情形之一成立:(ⅰ)如果u,v∈V(G),那么它们在G中邻接.(ⅱ)如果u,v∈E(G),那么它们在G中邻接.(ⅲ)如果u与v一个属于V(G)而另一个属于E(G),那么它们在G中不关联.文章给出了变换图G++-的连通度的一个下限.     

Cartesian积图的最大拉普拉斯特征值

设G=(V(G)),E(G)),H=(V(H),E(H))是两个简单的连通图,定义与的Cartesian积G×H图是:其顶点集为V(G×H)=V(G)×V(H),其中任何两个顶点(u,u’),(v,v’),相邻当且仅当u=v且u’,v’在H中相邻;或u’=v’且u,v在G中相邻,这里u,v∈V(G),u’,v’∈V(H).本文研究两个图的Cartesian图的拉普拉斯矩阵的最大特征值,得到如下结论:设简单图G具有n顶点m条边,图H具有P个顶点q条边,那么G和H的Cartesian积图G×H的拉普拉斯最大特征值p(L(G×H))≤2m/n[1+(n-1)(((n3/4m2)-(1/n-1))～(1/2))]+((2p-1)～(1/2))+1.     

关于二分图的F-Hamilton性

设G是一个简单图,任意e∈E（G）,定义e=uv在G中的度d（e）=d（u）＋d（v）,其中d（u）和d（v）分别为顶点u和v在G中的度数。设F是二分图G的一个1-因子,如果G中有包含F的Hamilton圈,则称G是F-Hamilton的;给出了二分图是凡Hamilton的一个新的充分条件。     

Cartesian积图的分解

若图G的边集能划分成两两不相交的若干个子集，使得每个子集都导出相同的子图H，则称G存在H分解。两个图G=（Vi,Ei）（i=1，2）的Cartesian积，记作G1□G2，其顶点集V=V1×V2，边集E={（（u1，u2），（v1，v2））｜u1=v1∈V1,u2v2∈E2或u2=v2∈V2，u1v1∈E1}。本文给出了路和圈的Cartesian积图存在只分解的充要条件。     

图的λ4-最优性的邻域交条件

文章给出了图的λ4-最优性的邻域交条件.设图G是阶至少为34的λ4-连通图,若对G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥6且ξ4（G）≤3n（G）/2＋3,则G是λ4-最优的;若对于λ4-连通图G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥6且对图中每个三角形T至少存在一个顶点v∈V（T）...     

图的λ_6-最优性的领域交条件

文章给出了满足一定条件的图的λ6-最优性的领域交条件.设图G是连通图,若对G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥10且｜X5｜≤5,则G是λ6-最优的;若对于连通图G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥10且对图中每个三角形T至少存在一个顶点v∈V（T）使得d（v）≥v2＋5,则G是λ6-最优的.     

Mycielski’s图的Co-PI指标

令G是一个图,u是图G的一个顶点, TG（ u）是图G当中除了u以外的其余顶点到点u的距离之和, T（ u）＝TG（ u）＝∑u∈V dG（u,v）,Co-PI指标定义为：Co -PIv（G）＝∑uv∈E（G） T（ u）-T（ v）。文章给出了一些Mycielski’ s图的Co-PI指标的计算公式。     

点可区别全色数的一个上界

设G是简单图，f是从V（G）UE（G）到{1,2，…，k）的一个映射．对每个u∈y（G），令c（u）={f（u）}v∈V（G）,uv∈ E（G）}．如果，是k-正常全染色，且对任意u，v∈V（G）（u≠v），有c（u）≠c（v），那么称f为图G的k-点可区别全染色（简记为k-VDTC）．数χvt（G）=min{k｜G-有k—VDTC}称为图G的点可区别全色数．通过应用概率方法，证明了对任意最大度A≥2的图G，χvt（G）≤32（△＋1）．     

当35≤d≤55时圈的d-强全染色（英文）

对于图G=(V,E)的一个正常全染色,用C(v)表示顶点v∈V的颜色以及与v关联的边的颜色构成的集合,称之为点v∈V的色集合.如果C(u)≠C(v),那么就说u和v被该全染色所区别.一个图G的d-强全染色是指使得满足1≤dG(u,v)≤d的任意一对顶点u和v可区别的一个正常全染色.所谓一个图G的d-强全色数是指对图G进行d-强全染色所需要的颜色的数目的最小值.文中对当d∈[35,55]时圈的d-强全色数进行了确定.     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G^＊满足V（G^＊）=V（G）,E（G^＊）=E（G）∪{uv：uv∈E（G）,且J（u,v）≠φ},这里J（u,v）={w∈N（u）∩N（v）,N（w）（∈）N[u]∪N[v]}.本文利用插点方法,给出了关于k,或（k＋1）-连通（k≥2）图G是哈密尔顿的,1-哈密尔顿的或哈密尔顿连通的统一证明.其充分条件是在图G中关于^k∑i=1｜N（Yi）｜＋b｜N（y0）｜与n（Y）的不等式,这里Y是图G的部分平方图G^＊的任一独立集,对于i∈{1,2,…,k},Yi={yi,yi-1,…,yi-（b-1）}（∈ ）Y（yj的下标将取模k）;b是一个整数,且0＜b＜k＋1;n（Y）=｜{v∈V（G）,dist（v,Y）≤2}｜.