有圈图反比度的上下界

研究了单圈图、双圈图的反比度,给出了它们的上下界并得到达到最大最小值的极图,还进一步给出多圈图的上下界的一个猜想。     

关于树的几何反比度的一个猜想

证明了张玉忠,周厚春文中的一个猜想,设Ｔ为ｎ个点的树,则Ｔ的几何反比度Ｒｃ（Ｔ）≤１／２（ｎ＋２√２－３）,ｎ≥３,且对于特殊情形,得到比猜想更好的结果,从而说明春猜想对于树是成立的。     

一类极大临界h连通图

讨论了最小度等于３ｈ／２－１的极大临界ｈ连勇图的性质，并给出这类图的构造方法。     

定向图连通度的下界

有向图和二部有向图连通度的下界已由Hellwing和Volkmann给出.定向图是没有二圈的有向图.文章研究了这类特殊的有向图-定向图,同时通过改进Hellwing等人的证明方法,得到了定向图和二部定向图连通度的更好的下界.     

强乘积图的连通度

用k1＞0和δi表示图Gi(i=1,2)的连通度和最小度,给出了无向图强乘积的连通度一个下界κ(G1(□×)G2)≥min{κ1(1+δ2),k2(1+δ1)}.     

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

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

变换图G++-的连通度

本文所研究的图G的变换图G++-是以V(G)∪E(G)作为顶点集的图,它的两个顶点u与v被一条边连接当且仅当下列情形之一成立:(ⅰ)如果u,v∈V(G),那么它们在G中邻接.(ⅱ)如果u,v∈E(G),那么它们在G中邻接.(ⅲ)如果u与v一个属于V(G)而另一个属于E(G),那么它们在G中不关联.文章给出了变换图G++-的连通度的一个下限.     

关于图的谱半径与连通度

给出了图的邻接矩阵和拟-Laplacian矩阵分别依赖于点连通度、边连通度和顶点最小度的最大特征值的一些紧的上界，且得到了所有的极图。     

连通图的度距离和Wiener指数

令P+(n)表示圈没有公共边的n阶连通图的集合,P+(n,m)表示P+(n)中具有m(m≥1)个极小圈的连通图集合.证明了当n≥6时,P+(n,m)中具有最小度距离的图是花F(n,m),它是m个具有一个公共顶点的三角形并在公共顶点粘上n-1-2m条悬挂边的图;同时证明P+(n)中具有最小度距离的图是F(n,1),它是一个三角形并在一个顶点上粘n-3条悬挂边的图.     

k—连通图为Dλ—连通的一个充分条件

本文在对有限简单图给出 D_λ—连通的定义之后,证明了下述定理:设 G 是n 阶 k—连通(k≥3)的有限简单图,如果对任意的 Y∈I_k(G,λ),有sum from i=1 to k (k+i-2)/(k-1)s_i(Y、λ)>n-k(λ-1),则 G 是 D_λ—连通的.     

收缩临界6连通图中的6度顶点

如果6连通图的一条边收缩后使得所得到的图仍是6连通,则这条边称为6可收缩边.一个不包含6可收缩边的非完全图被称为收缩临界6连通图.由Egawa的结果可知收缩临界6连通图中有6度点.设G是收缩临界6连通图,用V6表示G中6度点的集合.Ando等人通过证明存在常数c使得|V6|＞c|V(G)|且c≥(1)/(7).现将这一常数改进为c≥(1)/(5).     

Ore－型子图对图的Hamilton性的影响

设Ｇ＝（Ｖ，Ｅ）为ｎ阶２－连通的１－坚韧图。将Ｇ的节点分类：ｇ＝｛ｖ∈Ｖ｜ｄＧ（ｖ）≥ｎ／２｝而Ｈ＝（Ｇ＼ｇ）。如果Ｈ满足Ｏｒｅ－条件：ｘ，ｙ∈Ｖ（Ｈ），（ｘ，ｙ）∈Ｅ（Ｈ）ｄＨ（ｘ）＋ｄＨ（ｙ）≥｜Ｖ（Ｈ）｜，则有：（ｉ）Ｇ是Ｈａｍｉｌｔｏｎ的；（ｉｉ）若Ｇ不是偶图，则Ｇ至多丢失长为ｎ－１的圈．     

连通图划分定理及其在图计数中的应用

本文证明了关于连通图划分的一个定理.运用这个定理,简化了标号连通图和标号树的递归计数关系的证明,并导出了给定价数和根点块数的有根标号连通图和二色标号连通图的递归计数式.     

多重路径与多重圈笛卡尔乘积图的联结数

本文给出了多重路径与多重圈笛卡尔乘积图联结数的计算公式,并给出了证明.     

一个关于2─连通图周长的次条件

设Ｇ为ｎ阶２－连通图，顶点ｖ１，ｖ２，…，ｖｎ满足ｄ１≤ｄ２≤…≤ｄｎ，其中ｄｉ＝ｄ（ｖｉ），ｉ＝１，２，…，ｎ。给出ｃ（Ｇ）≥ｍｉｎ｛ｎ，ｍ｝的如下条件：     

K连通图的k分割多项式算法

图G的K分割问题可描述为:输入(Ⅰ)G=(V,E),G为简单无向图,其中|V|=n,|E|= m;(Ⅱ)a_1,a_2,…,a_k k个G中不同的顶点;(Ⅲ)n_1,n_2,…,n_k k个正整数满足 n_1+n_2+…,+n_k= n.输出(V_1,V_2,…,V_k),对1≤i≤k,满足(Ⅰ)a_i∈V_i;(Ⅱ)G[V_i]是连通图;(Ⅲ)|V_i|=n_i.本文给出时间复杂性为O(knm)通用K连通图的k分割多项式算法.     

最少边数的n阶3-点连通简单图及其构造

从图的度数列入手,采用一种特殊的构造方法,不仅得到了3-点连通简单图的最少边数c(G)的值,还得到了图的边数最少时的连通简单图.     

有向图超级边连通性的倒数度条件

有向图D称为超级边连通的,若每个最小边割都是由发自某顶点的边组成,或由发至某顶点的边组成．没有零度点的有向图D的倒数度为R（D）=∑veV（D）（1／d（v））．笔者给出有向图的超级边连通性的倒数度条件．不同的例子将说明这些条件是最好可能的．     

广义轮型完全多部图的生成树数

证明了如下结论:设KWk,n是由轮图集W={Wn1,Wn2,…,Wnk}生成的n阶广义轮型完全k-部图,其中n={n1,n2,…,nk},n=|n|=n1+n2+…+nk,1≤k≤n.那么KWk,n的生成树数目为t(KWk,n)=n2k-2∏ki=1αni-1i+βni-1i-2n-ni+1,其中αi=(di+d2i-4)/2,βi=(di-d2i-4)/2,di=n-ni+3.     

4—线连通简单图的一个构造方法

本文给出4-线连通简单图的一个构造方法,这是一个涉及图的连通性研究方面尚未解决的问题。