连通3—控制临界图的小度点数

本文给出连通3-控制临界图度小于等于2的顶点个数的最小上界为3。     

图的全色数强色数和点荫度

利用图标的方法得到图的全色数的一个上界，并证明其是可达的。其次给出图的强色数的一个上界，并对极图予以刻划，最后对图与补图的点荫度之间的关系给出一个简单的证明。     

图的控制数与点线荫度的关系

该文给出了图的控制数与2倍点线荫度之和及积的上界且所给出的界均可达到。     

边数较少的图的线性荫度

设G是一个连通图且满足|E|≤|V| [3△／2]-4,则它的线性荫度la(G)=[△／2],同时得到了一个与树相关的结果。     

图和补图的荫度

本文研究了图和补图荫度间的关系,并猜想:对p阶简单图G(V,E),有 a(G)+a(G~c)≤1+[p/2] 其中G~c表示G的补图,a(G)表示G的荫度,[x]表示不小于x的最小整数。     

有限图的边荫度分解

设有限图Ｇ＝（Ｖ,Ｅ）,Ｐ＝｛Ｖ１,Ｖ２,．．．,Ｖｒ｝为Ｇ的一个划分,收缩Ｖｉ为点ｖｉ（ｉ＝１,．．．ｒ）,得到Ｇ的收缩图Ｇｐ＝（Ｖｐ,Ｅｐ）。文中通过对Ｇ递归地进行收缩,改进了Ｇ的边不重生成树数目的上界,并给出了Ｇ的边荫度分解的具体方法。     

乘积图的荫度

研究了乘积图的荫度并对一般的图G ,H ,给出了其乘积图G×H 荫度上界 .对一些特殊图类的乘积图 ,给出了其荫度的显性表达式     

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

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

图的点线荫度

图G的顶点集V(G)划分为一些子集,使得每个子集的导出子图是0线森林(即每个分支是路)的最小子集数叫图G的点线荫度,记为v|a(G).Poh K S证明了任何平面图的点线荫度最多是3.Matsumato M给出了图的点线荫度的上界,即v|a(G)≤[△(G)/2].这里△(G)是G的最大度.本文给出了完全n部图的点线荫度计算公式,同时也给出了任意图的点线荫度的精确上下界．     

有限图的边荫度分解

设有限图Ｇ＝（Ｖ，Ｅ），Ｐ＝｛Ｖ１，Ｖ２，…，Ｖｒ｝为Ｇ的一个划分，收缩Ｖｉ为一点ｖｉ（ｉ＝１，…，ｒ），得到Ｇ的收缩图ＧＰ＝（ＶＰ，ＥＰ）．文中通过对Ｇ递归地进行收缩，改进了Ｇ的边不重生成树数目的上界，并给出了Ｇ的边荫度分解的具体方法     

Halin图的线性2-荫度

图G的线性2荫度la2(G)是将G分解为k个边不交的森林的最小整数k,其中每个森林的分支树的长度至多为2的路.给出了Halin图G的线性2荫度.     

整数距离图G(Dm,3)的点荫度

整数距离图G（D）以全体整数为顶点集,顶点u,v相邻当且仅当｜u—v｜∈D,其中D是一个正整数集．对于m〉3,设Dm,3={1,2,…m}＼{3},得到了G（Dm,3）的点荫度的上界和下界并决定出了它在某些m上的确切值．     

3连通图的可去边的分布

e是3连通图G的一条边,如果G-e是某个3连通图的剖分,则称e是G的可去边。研究了3连通图的去边的分布规律,得到：（1）是阶至少为6的3连通图G中的一个圈,如果C上不存在3个连续的3度点,那么C上至少有两条可去边。（2）设T是阶至少为5的连通图G的一棵生成树,如果G中至多存在一个极大半轮,那么T上至少有一条可去边。由此可得：阶至少为5的3连通3正则图的生成树上至少有一条可去边。     

五面体平图中的生成树的构造与计数

首先给出了生成子图的定义,生成子图与生成树、含圈的生成子图的关系S(G)=C(G)+T(G);其次对于任意连通图,以p=4,q=6的完全图K4为例给出了生成子图个数的计算公式,同样以p=4,q=6完全图K4为例给出了生成树的构造定理和计数定理,提出了图S(G)生成树的计数方法和构造方法;最后,介绍了五面体平图生成子图个数的计算和各生成子图的构造,并验证了所给公式的正确性,从而解决了任意平图G(p,q)生成树的构造问题。     

整数距离图G(D_(m,30)的点荫度

整数距离图G(D)以全体整数为顶点集,顶点u,v相邻当且仅当|u-v|∈D,其中D是一个正整数集.对于m>3,设Dm,3={1,2,…m}\{3},得到了G(Dm,3)的点荫度的上界和下界并决定出了它在某些m上的确切值.     

一类整数距离图的点荫度

整数距离图以全体整数作为顶点集，顶点u、υ相邻当且仅当｜u-υ｜∈D，其中D是一个正整数集．对于m〉3，令Dm=[1,m]／[1,3]．本研究得到了G（Dm）的点荫度．     

无爪图中子图的度和与Hamilton圈

定义了子图的度的概念,证明了如下结果：设图G是n阶2-连通无爪图,如果G中任意两个同构于心的不相邻子图日,也的度和d（H1）＋d（H2）≥n-2,则G有Hamilton圈．     

一类凯莱图的2—边临界性

设Г是奇数阶阿贝尔群上的４－正则连通凯莱图，讨论了Г－｛ｅ１，ｅ２｝的边着色问题，其中ｅ１，ｅ２是Г的任意两边，通过研究了Г的哈密顿分解，得出如下结果；对Г的任意两条边ｅ１，ｅ２，存在Г的一个哈密顿分解分离ｅ１，ｅ２；进而证明了Г－｛ｅ１，ｅ２｝是第一类的。     

嵌入曲面的图的点荫度

图 G 的导出森林 k-划分是指其顶点集 V（G）的一个 k-划分（V1,V2,…,Vk）,使得对于每个 i（1≤i≤k）,导出子图 G[Vi]是一个森林。图 G 的点荫度是使得图 G 有导出森林 k-划分的最小的正整数 k,记为 va（G）。主要证明了如果图 G 能够嵌入到欧拉示性数非负的曲面上,则当图 G 满足三类条件时,可以得到 va（G）≤2。