简单图类的生成树数（Ⅰ）

连通图的生成树是该图的极小连通生成子图．本文通过Ｃａｙｌｅｙ公式及求解递推关系方程，分别求出了三类简单外平面图Ａ＿ｍ，Ｂ＿ｍ和Ｚ＿ｍ的生成树的棵数，给出了它们的递推关系式及通项表达式．     

若干图类的生成树数

连通图的生成树是该图的极小连通生成子图。本文求出了所有梯形图、扇形图和轮形图生成树的棵数，分别给出了它们的递推关系式和通项表达式．     

简单有向连通图关联矩阵右逆的图特征及应用

研究ｎ阶简单有向连通图的ｎ－１传导矩阵,引入了图真值向量及运算,得出ｎ阶简单有向连通图关联矩阵右逆的图特征;提出了一种寻找简单有向连通图全部生成树的方法。     

某些伪类环图的生成树数

连通图的生成树是指该图的极小连通生成子图.通过Cayley公式、递推关系式及伪类环图与伪类环图生成树数之间的关系式给出伪类环图-Sn,-An的生成树数.     

n连通图的可收缩边

ｎ连通图的可收缩边，人们分别在图中无三角形及图Ｇ的最小度≥３／２ｎ－１时等情况中，给出了边数下界，利用边断片给出了ｎ连通图在边原子阶≥ｎ／２时可收缩边的下界，进而给出在最小度≥４／３ｎ－１时的边数下界。     

平面格图生成树的计数

设ｔ（ｍ,ｎ）和ｔ（ｍ,ｎ）分别是平面ｍ×ｎ格图生成树和对称生成树的数目,从而给出了ｔ（３,ｎ）和ｔ（３,ｎ）的闭公式以及ｔ（ｍ,ｎ）递推式阶的估计．     

利用对偶图求平面图的生成树数目

图的生成树数目是图的一个重要参数，求连通图生成树数目的方法有很多．本文利用平面图的对偶图的Kirchhoff矩阵来求一些平面图的生成树数目，求这类平面图的生成树数目比直接利用收缩边和去边得到递推公式的方法要简单，该方法对于平面图可以进一步推广.     

关于Faudree－Schelp定理的改进

一个图Ｃ＝（Ｖ，Ｅ）是［ｌ，ｍ］－泛连通的，如果在Ｇ的任意一对节点ｘ与ｙ之间有长为Ｋ—１的路Ｐｋ（ｘ，ｙ），Ｋ＝ｌ，ｌ＋ｌ，…，ｍ。Ｇ具有性质Ｐ（Ｋ），如果对Ｇ的任何一对距离为２的节点ｘ和ｙ，有ｄ（ｘ）＋ｄ（ｙ）≥Ｋ。作者探讨了一类产（Ｋ）图的路连通性，改进了Ｆａｕｄｒｅｅ－Ｓｃｈｅｌｐ定理，得到两个定理：定理１设Ｇ＝（Ｖ，Ｅ）是ｎ阶Ｐ（ｎ—１）图。如果Ｇ是［ｎ—１，ｎ］－泛连通的，则Ｇ是［８，ｎ］－泛连通图（ｎ≥８）．定理２设Ｇ是３－连通ｎ阶Ｐ（ｎ）图。如果Ｇ的独立数α（Ｇ）＜ｎ／２，则Ｇ是［５，ｎ］－泛连通图，ｎ≥５．     

关于环形街道图 H_(n_1×n_2)∶n_1=3,n_2=6,8,10,12,14 的最优强连通定向

本文研究由城市环形街道所引起的强连通定向（单行道设计）图的问题，即研究由ｎ１条环形道和从中心向外辐射的ｎ２条路组成的城市街道图。将按直径最优的准则寻求最优强连通定向。本文解决了ｎ１＝３，ｎ２≡０（ｍｏｄ２），６≤ｎ２≤１４时的情形，得到了全部最优强连通定向。     

28个顶点的简单MCD图

设Ｓｎ是ｎ个顶点的没有等长圈的简单图的集合．若Ｇ∈Ｓｎ且Ｓｎ中不存在图Ｇ＇使｜Ｅ（Ｇ＇）｜＞｜Ｅ（Ｇ）｜，则称图Ｇ是简单ＭＣＤ图．若简单ＭＣＤ图Ｇ是２连通的，则称Ｇ是２连通简单ＭＣＤ图．本文证明了不存在具有２８个顶点的含有同胚于Ｋ４的子图的２连通简单ＭＣＤ图．于是结合ＤｉｓｃｒｅｔｅＭａｔｈ．１２６（１９９４），我们完全证明了下述定理：存在ｎ个顶点的含有同胚于Ｋ４的子图的２连通简单ＭＣＤ图当且仅当ｎ∈｛１０，１１，１４，１５，１６，２１，２２｝．     

强连通二部分竞赛图和可约二部分竞赛图计数

设Ｔ（ｍ，ｎ）表示不同构的ｍ×ｎ二部分竞赛图的个数，借助Ｔ（ｍ，ｎ）导出了不同构的强连通ｍ×ｎ二部分竞赛图的数目及同构的可约ｍ×ｎ二部分竞赛图的数目公式。     

强连通图的二阶指数集

设Ｄ为ｎ阶强连通图，Ａ（Ｄ）为Ｄ的邻接矩阵，则以Ａ（Ｄ）＋Ａ~２（Ｄ）为本原矩阵，其指数称为Ｄ的二阶指数，ｎ阶强连通图的二阶指数集Ｓ（２，ｎ）＝｛１，２，…，ｎ－１｝。     

竞赛图的本原指数及其极图刻划

设Ｄ为ｎ阶强连通竞赛图，证明了当ｎ≥５时，Ｄ的本原指数３≤ｒ（Ｄ）≤ｍ＋２，并给出了达到最大值ｎ＋２的极图的一刻划及达到最小值３的科的荐干条件。     

某些偶数度循环图的同构因子分解

根据连通循环图的性质，证明了循环图的同构因子分解，对于某些偶数度循环图结论成立，得到了Ｃｎ〈ｊ１，ｊ２，…，ｊｒ〉及Ｃｎ〈１，２，…，ｒ〉的同构因子分解条件．     

强哈密尔顿的一个结果

本文中我们获得泛连通图的一个结果。设Ｇ是ｎ阶简单图，若　≥ （ｎ＋１）／２，则Ｇ是泛连通图或Ｇ＝Ｋ（ｎ－１）／２　　Ｋ（ｎ＋１）／２。此结果比１９７７年Ｊ· Ｗｉｌｌｉａｍｓｏｎ 得到的结果好。     

循环图的连通度

根据循环图的原子部分的性质，得出了循环图Ｇ＝Ｃｎ〈ｊ，ｊ２，…，ｊｒ〉的连通度Ｋ（Ｇ）的求法及连通度Ｋ（Ｇ）≥ｗ（ｗ＝ρ（Ｇ））的循环图的构造方法     

关于图的泛连通性的几个结果

如果对ａ≤ｉ≤ｂ，图Ｇ的任一对顶点ｕ、ｖ都存在长为ｉ－１的路Ｐｉ（ｕ，ｖ），则称Ｇ是［ａｂ］－泛连通的．文中证明了关于图的泛连通性的下述结果：设Ｇ为ｎ阶连通图，且对Ｇ中任一对距离为２的顶点ｕ，ｖ，有ｄ（ｕ）＋ｄ（ｖ）≥ｎ，则图Ｇ是［５ｎ］－泛连通的当且仅当Ｇ是Ｈ连通的．此结果推广了Ｆａｕｄｒｅｅ和Ｓｃｈｅｌｐ的一个结论．     

一类OF图及其泛连通性

设Ｇ为ｎ阶连通图，且对Ｇ中任一对距离为２的顶点ｕ、ｖ，有ｄ（ｕ）＋ｄ（ｖ）≥ｎ，则称Ｇ为ＯＦ图．本文讨论了ＯＦ图的泛连通性，主要得到下列结果：设Ｇ为ｎ阶ＯＦ图，则Ｇ为下列三类图之一：（１）Ｇ是［５ｎ］－泛连通图（２）Ｈ＋；（３）Ｋｍ＃Ｋｎ－ｍ＋２及其部分支撑子图，其中３≤ｍ≤ｎ－１，｜Ｖ（Ｈ）｜＝．     

图的度序列与Hamilton连通性

引进图的弱闭包的概念，证明了：设ｎ阶３－连通图Ｇ的度序列为ｄ１≤ｄ２≤…≤ｄｎ，如果对任意ｋ由，ｄｋ≤ｋ＋１可推出ｄｎ－ｋ≥ｎ－ｋ，那么Ｇ是Ｈａｍｉｌｔｏｎ连通图。     

完全图半群与连通图半群

引进了拟完全国半群、完全图半群、连通图半群以及连通元的概念，证明了有限字母在上的自由半群和相应的完全图半群同构；是可换图。另外，给出了ｎ阶连通简单图半群有Ｓ阶完全子图半群的一个充分条件。