平方根图

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

边面染色数为3的一个充分必要条件

在图的边面染色中,使得两相邻元素染不同颜色所需的最小色数,称为平图的边面染色数,首先系统地证明:假设是最大度为3的二连通平图,则边面染色数与最多度相等的充分必要条件是是一个2-连通3-正则二分平图,然后得出结论:任何连通平图,其边面染色数为3的充分必要条件是阶至少为三的一条路或2连通3正则二分平图。     

正则图的环边连通性和环连通性之间的关系

研究了一般3 正则连通图G的环边连通性和环连通性之间的关系,证明了G的环边连通度等于其环连通度。讨论了G的环连通度与环点连通度之间的关系,指出当G的顶点个数不少于其环连通度的6倍时,其环连通度等于其环点连通度。     

一种构造紧图的方法

根据一些已知的紧图构造出两类新的紧图。证明了在一定条件下连通正则紧图的联图为紧图,两个连通正则紧图之间再加一条边仍为紧图。     

正则图的代数连通度

设G=(V,E)是一个具有n个顶点的简单图,A(G)是G的邻接矩阵,D(G)表示G的度对角矩阵,图G的拉普拉斯矩阵定义为L(G)=D(G)-A(G).若矩阵L(G)的特征值为μ1≥μ2≥…≥μn-1≥μn=0,则称μn-1为G的代数连通度.研究了正则图的代数连通度,得到了下列结论:μn-1≤(nrln(n-l))/(6n-8-4r-nln(n-1))这里,r表示正则图的度.     

图是极大限制边连通的一个充分条件

设G是n阶简单无向连通图,G的限制边割是删除它以后G不连通,且留下的每个分支不含孤立点的边子集;限制边割的最小基数称为限制边连通度.记G的顶点x的度为d(x)。证明了若对超级连通图G中任意一对不相邻的顶点x和y都有d(x) (dy)n,则G是极大限制边边通的当且仅当G不同构一种特殊图G。     

2p2阶4度Cayley图

Cayley图Cay(G,S)称之为正规的,如果G的右正则表示R(G)是Cay(G,S)全自同构群的正规子群。决定了2p2(p为奇素数)阶群上4度连通1-正则Cayley图的正规性。     

关于图的超常边连通度和等周边连通度的等值性

图的超常边连通度和等周边连通度是图的通常边连通度概念的推广，首先举例说明在一般情形下两者可以不等，然后再论证明当正则边可迁图的阶不小于3k时，它的k阶超常边连通度与k阶等周边连通度相等。     

一类无三角正则图的性质

图为无三角正则图,它满足不相邻的顶点恰有两个公共相邻顶点.先从代数的角度去研究它的特征值,得到了它的顶点个数只能取一些特殊的整数,然后证明了其点连通度与边连通度相等,而且存在完美匹配,最后猜想:(1)x(G)=x'(G)=k;(2)图G是Hamilton图.     

完全二部图K3,3的s-正则二面体覆盖

将图称为s-正则的,如果它的自同构群作用在它的s-弧集上是正则的．Feng和Kwak分类了6阶完全二部图K3．3上保纤维自同构群弧传递的连通s-正则循环覆盖．现在,证明了不存在K3.3上保纤维自同构群弧传递的连通s-正则二面体覆盖．     

关于积图的点连通度

研究了积图的点连通度,并给出了积图点连通度的一个新的下界:设Gm和Gp分别是构成积图Gm*Gp的主图与模型图,若Gm是一个有m个点的连通图,则κ(Gm*p)≥min{mκ(Gp),δ(Gp)+1}.     

基于邻接矩阵图的连通性判定准则

利用图论和集合论的知识，对节点邻接矩阵进行深入分析，提出了有向图和无向图的连通性判定推则及图中任意两节点间不连通的判定准则：对路径及节点邻接矩阵的概念进行了更为严格的数学描述；确定了路径的极限长度。文中提出的图的连通性判定准则具有程序思想简单、逻辑性强、方便快捷的优点，对于图的连通性判定、连通块的划分等都具有指导意义。     

连通图二次幂图的Hamilton连通性

本文对圈和树的二次幂图的 Hamilton 连通性进行了研究。     

关于图的可达划分数

本文给出了E.J.Cockayne和S.T.Hedetniemi的下列猜想的一个新证明:当图G的团图为2-分图时,G的最小团的阶数不大于G的可达划分数;讨论了图的可达划分数与连通度的关系。     

循环图的直积分解

本文讨论了 Cayley 图的直积不变性,进而得到了一个循环图可分解为若干个循环图的积图的充要条件,并旦得到了两个正则有向图的连通度与它们的积图的连通度的关系。     

有关连通度一定理证明方法的探讨

有关图的连通度结论k(G)≤λ(G)≤δ(G),在图论中是一个很重要的定理,下面用一种与传统证明方法不同的新方法对此定理进行了证明.     

度在无向图中的简单应用

在已有文献基础上,计论度在判断无向图的圈、连通性、Euler图以及Hamilton图等方面的一些运用．     

双圈图的N—G型的代数连通度的界

对任一个凡阶单图G,用0（G）表示G的代数连通度,Gc表示它的补图．针对双圈图．即边数等于顶点数加1的且只含有2个边不交的基本圈的简单连通图,证明了对任一n阶双圈图G,有1≤a（G）＋a（G^C）,当且仅当3G兰G1时等式成立．     

含有两个基本圈的简单图的N-G型代数连通度的界

对任一个n阶简单图G,用a（G）表示G的代数连通度.在已有文献研究的基础上,通过分类研究和个别图具体研究,证明了对任一含有两个基本圈的简单图G,有1≤a（G）＋a（Gc）.