边韧性度的理论综述

主要概述了边-韧性度产生的背景与过程;到目前为止边-韧性度所获得的基本理论有：边韧性度的界;一些特殊的边韧性度图;边韧性度图的充分必要条件．指出了它的发展前景及目前有关研究方法和课题：即最大和最小边韧性度图;非边韧性度图的边韧性度;边韧性度与其他参数,如直径和边整度之间的关系.     

完全多部图和笛卡儿积图的线性点荫度

图的线性点荫度是对它的顶点进行染色所用的最少颜色数,同时使得染同一种颜色的点集所导出的子图,它的每个分支均为路．本文完全确定了完全多部图的线性点荫度,给出了笛卡儿积图的线性点荫度的一个上界,得到了一些特殊图（ 如路,圈和完全图） 的笛卡儿积图的线性点荫度．     

乘积图的荫度

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

给定匹配数的图的代数连通度的上界

【目的】确定给定匹配数的n个点图的拉普拉斯代数连通度的上界与该上界所对应的极图。【方法】首先，利用图的匹配数与奇连通分支个数的关系与图的变换等方法刻画了给定匹配数的n个点图的拉普拉斯代数连通度上界所对应的极图；其次，利用具有相同邻点集的图与对应特征值的关系得到给定匹配数的n个点图的拉普拉斯代数连通度上界。【结果】借助图与补图的关系以及拉普拉斯特征方程证明得到给定匹配数的n个点图的拉普拉斯代数连通度的上界与该上界所对应的极图是一一对应且唯一确定的，从而同时确定了给定匹配数的n个点图的拉普拉斯代数连通度的上界以及此上界所对应的极图。【结论】用全新的方法同时确定了给定匹配数的n个点图的拉普拉斯代数连通度的上界以及此上界所对应的极图，克服了以往利用图的最小度，最大连通度与代数连通度的关系只刻画了给定匹配数的图中具有最大代数连通度的图类特征，但无法得到此类图的连通度的上界这一弊端。     

图的Laplacian矩阵谱半径

设G为n阶简单连通图,若L(G)为图G的度对角矩阵与邻接矩阵的差,则称L(G)为图G的Laplacian矩阵.结合非负矩阵谱理论,利用图的顶点度和平均二次度给出了图G的Laplacian矩阵的谱半径的新上界,同时给出了达到上界的极图.     

一些可靠通讯网络的构造

本文首先得到了循环图的原子部分仍为连通循环图的结果,同时还得到了连通循环图的连通度的一些性质。然后应用这些结果与循环图的理论,得到了5,7,8,9度连通循环图的连通度等于其度数的充要条件,从而可构造出5,7,8,9度可靠通讯网络。     

具有乘积度-基尔霍夫指标极值的双圈图（英文）

对于一个图G,乘积度-基尔霍夫指标定义为R*(G)=∑{x,y}■V(G)dG(x)dG(y)rG(x,y).基于前人的一些研究成果,用类似于和的度-基尔霍夫指标应用在双圈图中的方法,把乘积度-基尔霍夫指标运用到双圈图中.首先给出了关于R*(G)的一些图变换,然后根据这些图变换,确定了恰好有两个圈的n阶双圈图的最小和最大的乘积度-基尔霍夫指标的值及其对应的极值图.度-基尔霍夫指标广泛应用于电流网络、化学、马尔可夫链和欧氏距离等各个方面.     

正则图的Q-图的(度)基尔霍夫指标

由图G的Q-图的电阻距离和(乘法度或加法度)基尔霍夫指标的定义,讨论了图G的Q-图的(乘法度或加法度)基尔霍夫指标与图G的线图的基尔霍夫指标的关系,并给出了相应的例子。     

逆度和图的性质（英文）

设G=(V(G),E(G))是n个顶点m条边的简单图.无孤立点的图G的逆度定义为■,其中,d(v_i)表示顶点v_i的度.首先用逆度刻画了连通图分别是k-哈密尔顿、k-边哈密尔顿、k-路覆盖、哈密尔顿连通、k-连通、2-边连通和β-亏损的充分条件.其次用逆度给出了连通图的独立数小于等于整数k的充分条件.最后用逆度给出了连通的平衡二部图是哈密尔顿图的一个充分条件.     

仙人掌图的度偏差指数

为了研究图的非正则性,在已提出的度偏差指数s(G)=■(d_i表示顶点v_i的度)的基础上,通过图形变换研究了仙人掌图关于度偏差指数的极值问题,给出了它的极大值和极小值以及刻画了达到极值的仙人掌图。     

关于图的谱半径与连通度

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

图的Laplacian矩阵的谱半径

设G为n阶简单连通图，若Q（G）为图G的对角矩阵与邻接矩阵的和，称Q（G）为G的拟-Laplacian矩阵．讨论了Q（G）的性质并利用G的顶点数、边数、最大度和最小度给出了图G的Laplacian矩阵谱半径新的上界．     

图的Laplacian谱半径的一个新上界

设G为n阶简单连通图.若Q(G)为图G的对角矩阵与邻接矩阵的和,称Q(G)为G的拟-Laplacian矩阵.讨论了Q(G)的性质并利用G的顶点数、边数、最大度和最小度给出了图G的Laplacian矩阵谱半径的一个新上界.     

关于图的Laplacian谱半径的一个改进上界

设G为n阶简单连通图,若L（G）为图G的度对角矩阵与邻接矩阵的差,称L（G）为图G的Laplacian矩阵．本文利用图的度序列平方和与非负矩阵谱理论给出了L（G）的谱半径的一个新上界,改进了现有结果．     

图的扩张因子

图的扩张因子是度量图的连通性的一个重要参数.得到了图的扩张因子的上界和下界,刻画了达到上界与下界的图类,给出了n-维交叉超立方体和n-维增广立方体网络的扩张因子.     

一定条件下图的拉普拉斯矩阵的谱半径

研究给定阶、边独立数和圈数的类树图的拉普拉斯矩阵谱半径的精确上界,确定达到上界的所有的图,从而推广树、单圈图和双圈图拉普拉斯矩阵谱半径的结论.     

树的Laplace矩阵的最大和次大特征值

给出仅依赖阶数的树的Ｌａｐｌａｃｅ矩阵的最大和次大特征值的上界,并刻划达到上界的极图．     

图的双罗马控制数的界

定义在图G的顶点集V(G)上的函数f:V(G)→{0,1,2,3}称为G的双罗马控制函数,如果每个赋值为0的顶点至少与一个赋值为3或两个赋值为2的顶点相邻,并且每个赋值为1的顶点至少与一个赋值为2或3的顶点相邻。图的双罗马控制函数的权为所有顶点的赋值之和。双罗马控制函数的最小权称为双罗马控制数。利用顶点数、围长、周长以及最小度得到了含圈图的双罗马控制数的若干上下界。     

Halin图的一个点强全染色法

针对Halin图的点强全染色问题,提出一个有效的染色法———逐圈着色法,而且方法给出的方案也是最优的,即用最少的颜色完成Halin图的点强全染色.同时还确定了最大顶点度是3的Halin图的点强全色数的上下界,即上界为6,下界为5.