平方根图

设G是一个简单图及顶点为u1，u2，…，uv，d(vi)是点vi的度，令^～d(G)={[d(u1)]的平方根，[d(u2)]的平方根，…，[d(uv)]的平方根}，称G是一个平方根图，如果^～d(G)是G的邻接矩阵的一个特征向量，猜想：一个连通图G是一个平方根图的充分必要条件是G是一个正则图或半正则图，这个猜想在本文中得到了证明。     

几类特殊平面图的圈包装问题

给定一个无向连通图G，圈包装问题就是求G的边不相交圈的最大数目．此问题在一般图下是APX困难问题，在平面图下是NP困难问题．主要证明了在几类特殊的平面图下多项式时间可得到最优解．主要考虑外平面图，系列平行图和平面欧拉图这三类特殊的平面图．     

非色唯一的连通顶点可迁图的广泛存在性

本文中,我们构造性地证明了:对应于每一个给定的色唯一的连通顶点可迁图,均存在着无穷多个与之对应的非色唯一的连通顶点可迁图.据此,我们部分地回答了G.L.Chia在[4]中提出的第二个问题.     

半群Cayley图的乘积

证明了半群Cayley图的乘积图仍是半群Cayley图．由于（弱）点传递图的乘积图保持传递性，进一步得到结论：（弱）点传递的半群Cayley图的乘积图仍是半群Cayley图，并保持（弱）点传递性．     

一类包含优美树的优美图

设T_m是m个顶点的优美树,G_n是n个顶点的空留,证明了联图G_nVT_m是优美图．     

图之极小顶点覆盖

图的一个顶点覆盖被称为极小的假如其任何真子集不再是该图的一顶点覆盖，本文证明了某些图之所有极小顶点覆盖的个数的明确表达式，其中包括路径，梯形图，及线性ｎ部图。     

P-1阶图组相容的一个算法

本文给出关于Ｐ个Ｐ－１阶图组（Ｇ１，Ｇ２，…，Ｇｐ）相容的一个算法．     

利用状态空间进行问题求解

状态空间表示法是一种重要的知识表示方法。搜索是求解问题的一种有效的方法，而和搜索相对应的知识表示法一般有两种：一种是与或树表示法，另一种就是状态空间表示法。状态空间表示法可以利用状态空间求解问题的步骤及代价树的宽度优先搜索策略求解推销员旅行问题。     

一类本原双色有向图

研究了只有两个圈C1,C2的双色有向图.证明了这类双色有向图本原的充分必要条件,并给出了C2的顶点数为2时它的本原指数的下界.     

带有纽结分支的内在链图和内在纽结与3-链图

利用两个图K4,4-e与中间边组成的图来形成petersen图中的P8、P9和P10,构造出了带有纽结分支的内在链图.此外,笔者把内在纽结图和内在3-链图的性质结合起来,构造出了同时具有这两种性质的图,定义它为内在纽结与3-链图.该定义利用文献[1-4]引理证明,结论得证.