临界极大外平面图

给出了临界极大外平面图以及最大度临界极大外平面图的定义，并讨论了它们的性质，为研究极大外平面图的四染色提供了一种新方法。     

带参数可外平面图的一个算法

证明了顶点的权为参数t的线性函数,尺寸为n的可外平面图的最小顶点复盖的耗费函数的折点个数囿界于O(n~(?)),且提出了一个时间复杂性为O(n~(?))的求解算法。     

外可平面图的圈基结构

在ew（G）≥5的条件下。研究在平面和射影平面上2-连通的外可平面图的圈基结构,给出在这两种平面上嵌入的最小圈基,结果表明,平面上的最小圈基仅与面圈有关,射影平面上的最小圈基不仅与面圈有关,还与其不可收缩圈有着一一对应性。     

外平面图的平方图的点荫度

图G的平方图G2是以V(G)作为它的点集,两个点在G2中相邻当且仅当它们在G中的距离至多为2.证明了：若G是一个最大度Δ6的外平面图,则G2的点荫度va(G2)=「Δ+12?;特别地,一棵树T的平方图T2的点荫度va(T2)=「Δ+12?.     

外平面图的完备染色

设Ｖ（Ｇ）、Ｅ（Ｇ）和Ｆ（Ｇ）分别为平面图Ｇ的点集、边集和面集。Ｇ的完备色数Ｘｃ（Ｇ）是使得Ｖ（Ｇ）∪Ｅ（Ｇ）∪Ｆ（Ｇ）中相邻或相关联的元素间均染不同色的最少颜色数。本文证明了：对无割点的外平面图Ｇ，有Ｘｃ（Ｇ）≤ｍａｘ｛７，△（Ｇ）＋１｝，其中△（Ｇ）为Ｇ的最大度数。     

环面上外可平面图的最小圈基

研究环面上2-连通外可平面图G在嵌入∏的面宽fw(G)≥2时的圈基理论;给出在面宽fw(G)≥2和边宽ew(G)＞m,m=max{li|1≤i≤f}时外可平面图G的最小圈基的结构,其中f记为∏的除Hamilton圈外的面迹数,l1,…,lf为∏的对应面迹的长;并证明了G的最小圈基与其不同伦的两条长度之和最短的不可收缩圈之间存在一一对应.     

2-连通外平面图的邻点可区别全染色

运用数学归纳法及换色技巧,探讨了Δ(G)=7 的2-连通外平面图的邻点可区别全染色问题,使该问题在原有基础上得到了推广.     

外平面图的一个结构定理

给出了外平面图的拟对偶图的定义,并利用拟对偶图的性质证明了外平面图的结构定理。     

1-树与外平面图的无圈边着色

设f是图G的一个正常边着色，若在f下G中没有2-色圈，则称f是图G的一个无圈边着色，其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图，无圈边色数不超过其最大度加2。本文证明了该猜想对1-树与外平面图成立，且它们的色数均不超过最大度加1。     

最大度不超过4的2-连通外平面图的邻点可区别全色数

得到了最大度不超过4的2-连通外平面图的邻点可区别金色数．     

外平面图度有限制的k-荫度

令ak(G)表示最大度不超过k且能覆盖图G所有边的森林的最小数目.则对于任意的外平面图,当2≤k＜Δ(G)时有ak(G)=「Δ(G)/k.     

关于高度极大外平面图的4染色

从最大度的角度讨论两大极大外平面图的公共４染色，证明了当Ｇ是以ｒ个顶点的圈Ｑｒ为标定界环的极大外平面图且△（Ｇ）≥ｒ－２，Ｇ′是以Ｑｒ为标定界环的任一极大外平面图时，Ｇ和Ｇ′有公共４染色，从而证明了四色定理的等价例题在给定条件下成立。     

一类外平面图的有界染色

图G的k-有界染色是图G的一个最多有k个顶点染同一种颜色的顶点染色．图G的k-有界染色数χk(G)是指对图G进行k-有界染色所用的最少颜色数．讨论一类外平面图的k-有界染色，给出能在多项式时间内确定其k-有界染色数的一些充分条件．     

树和单圈图的Hosoya拓扑指标的界

一个连通图G=(V,E)的Hosoya指标H(G)=∑mk=0P(G,k)其中P(G,k)为图G的k匹配数,m是G中k可能取的最大值。目的系统讨论给定顶点的树和单圈图中H的最值问题,为充分估计并利用计算机搜索具有某种化学或物理性质的分子给出一个界值范围;重点讨论树的H值的计算问题,给出一个递归算法。方法利用组合数学和算法理论中的一些方法。结果1)H(Kn)≥H(G)≥n;H(Pn)≥H(T)≥n;H(Cn)≥H(G)≥H(K1*,n-1)。2)H(T)=H(T-R) ∑ki=1H(T-R-Ri)=∏ki=1H(TRi) ∑ki=1∏km=1∏kij=1H(TRm)H(TRij)。结论给出了树的Hosoya指标的一种递归计算方法。     

3连通图生成树上的可去边

摘要：设G是3连通图，e是G中的一条边．若G—e是3连通图的一个剖分．则称e是3连通图G的可去边．否则，称e是G的不可去边．本文给出某些3连通图的生成树上可去边的分布情况及数目。     

基于DPCNN的无向赋权图的最小生成树的求解

 利用脉冲耦合神经网络(PCNN,Pulse Coupled Neural Network)的脉冲波并行传播特性,在其时延脉冲耦合神经网络(DPCNN,Delay PCNN)的基础上提出了一种求解无向赋权图最小生成树的新算法.算法针对最小生成树的权值总和最小且连通的性质,结合时延脉冲耦合神经网络脉冲波的并行传播,通过求解无向赋权图的最短路径并对其连通性进行判断,采用迭代的方法,成功地求解了无向赋权图的最小生成树.最后给出了仿真实验,证明了该方法的有效性,与传统算法比较有一定的优势.     

优美图的嵌入

研究了优美与优美图之间的一种关系,每个优美图都可嵌入到另一个优美图中．通过构造证明了：设G1是任一个优美图,则必存一个优美图G2,使得G1是G2的真子图．这一结论给出了由一个优美图构造一类优美图的一种方法,并用此方法给出了几类优美图．