图拟拉普拉斯矩阵的特征值

G为有限无向简单图，A（G），D（G）分别表示G的邻接矩阵和度对角矩阵。Q（G）＝D（G）＋A（G）称为图G的拟拉普拉斯矩阵，它是谱图论的研究对象。本利用G的顶点数，边数，最大度和最小度给出Q（G）的最大特征值和最小特征值的界的估计。     

图的拟拉普拉斯特征多项式的系数

设G是一个简单无向图,A是图G的邻接矩阵,对角矩阵D=diag(dl,d2,…,dn)是G的顶点度矩阵,则L+=D+A称为G的拟拉普拉斯矩阵.本文研究了G的拟拉普拉斯矩阵的特征多项式QG(μ)的系数,利用图G的边数、度序列和三角形个数给出了QG(μ)的一些系数的代数表达式.     

连通图的拟拉普拉斯谱半径的一个上界

对于连通图G,矩阵Q(G)=D(G) A(G)称为图G的拟拉普拉斯矩阵,其中D(G)为图的度对角矩阵,A(G)为图的邻接矩阵.本文利用矩阵的一些性质,推导出连通图的拟拉普拉斯谱半径的一个上界.并将该上界与已有的一些结论结合具体图例作了优越性比较.     

关于图的拟拉普拉斯谱的标记

给出正则图的拟拉普拉斯谱的一些性质,研究图的拟拉普拉斯特征值重数的关系,得到mG#Sk(k)=mG(k),mG∧p3(1)=mG(1)。     

图的拟拉普拉斯永久多项式

设Ｇ是一简单无向图，Ｃ（Ｇ）表示Ｇ的关联矩阵，Ｑ（Ｇ）＝Ｃ（Ｇ）Ｃ（Ｇ）＾ｔ称为Ｇ的拟拉普拉斯矩阵，该文研究了永久多项式ｐｅｒ〔ｘＩ－Ｑ（Ｇ）〕。     

图的路(无符号)拉普拉斯谱半径及其能量

图G的顶点集V(G)={v₁,v₂,…,v_n},其路矩阵记为P(G)=(p_ij)_n×n,p_ij表示图中v_i,v_j之间内部顶点不相交路径的最大数目。定义路拉普拉斯矩阵和路无符号拉普拉斯矩阵并得到了其谱半径和能量的界。     

关于图的拉普拉斯能量的若干结果

研究图的拉普拉斯能量和拉普拉斯矩阵的奇异值之间的关系。确定了图的拉普拉斯能量的界,以及边和点的去除对能量值的影响。所得结果可用于研究理论化学中的分子能量。     

图的拟拉普拉斯矩阵前k个最大特征值和的上界

研究了简单连通图的拟拉普拉斯矩阵前k个最大特征值的和,并利用图的度序列和阶数给出了该和的一个上界。     

图的最大拉普拉斯特征值的上界

设G=(V,E)是n阶简单连通图,D(G)和A(G)分别表示图的度对角矩阵和邻接矩阵,L(G)=D(G)-A(G)则称为图G的拉普拉斯矩阵。利用图的顶点度和平均二次度结合非负矩阵谱理论给出了图的最大拉普拉斯特征值的新上界,同时给出了达到上界的极图,并且通过举例与已有的上界作了比较,说明在一定程度上优于已有结果。     

图的路覆盖数的上界

设G是简单图。记ρ(G)为覆盖图G所需路数的最小值。本文证明了ρ(G)≤[2n/3];且若G是连通图,则ρ(G)≤[3n/5]。     

图的ISI指数与能量的界

运用一些熟知的不等式,研究图的ISI指数与能量的上下界,通过考虑ISI指数和能量与图的不变量(最大度、最小度、边度等)和一些已知的拓扑指数之间的关系,从而得到图的ISI指数与能量的一些新上下界。     

利用不变量作二次曲线的图形

给出了用不变量及主直径作出二次曲线的图形的方法     

一种用于求图的带宽上界的标号方法

在图的水平构形概念的基础上，结合求最短路的Ｄｉｊｋｓｔｒａ方法，提出一种用于求图的带宽上标号方法，其主要内容为：１）用Ｄｉｊｋｓｔｒａ方法求同关于每一个顶点的水平构形；２）将选用的水平构形的每一个水平集Ｌｉ分成互不相交的两个子集Ｌｉ＾（１），Ｌｉ＾（２）先对Ｌｉ＾（１）标号，再对Ｌｉ＾（２）标号。     

图的距离谱半径的界

图的邻接谱、拉普拉斯谱已得到了广泛的研究,但关于图的距离谱的研究结果却很少。本文给出了距离谱半径的可达上下界为min i,j=1,2,…,n{(kikj)~(1/2)}≤u(G)≤max i,j=1,2,…,n{(kikj)~(1/2)}     

混合图的边着色

著名学者Daniel Krlá.,Jan Kratochvlí,Heinz-Jürgen Voss等曾在其著名论文《Mixed hypergraphs with bound-ed degree：edge-coloring of mixed multigraphs》中提出任何一个混合超图均可一一对应地转化成一个最大度不超过3的混合超图,且它们的着色亦是一一对应的。因此,研究最大度为3的混合超图的着色问题具有一般性,是困难的;而研究最大度为1的混合超图的着色问题是平凡的;所以我们着力研究最大度为2的混合超图。而最大度为2的混合超图的点着色问题可以一一对应地转化为一个与其对应的混合多重图的边着色问题,因此,文章从特殊的混合多重图-混合图入手,着力研究混合图的边着色。     

图与其补图特征值之和的界

设G是n阶简单图,其补图记为G^c,λi（G）为G的第i大特征值。文中给出了图与其补图几个常见的特征值之和的界（i=1,2,…,n）：-√2（n-1）（i-1）/（n-i＋1）≤λi（G）＋λi（G^c）≤√2（n-i）（n-1）/i （Ⅰ） 及 （n-1）≤λi（G）＋λ1（G^c）≤-1＋√1＋2n（n-1） （Ⅱ） （Ⅱ）式中,下界可达当且仅当G为正则图。     

图与其补图的Q谱半径之和的界

本文给出了图与其补图Ω谱半径之和的一个上界，给出了半正则二部图与其补图Ω谱半径之和的上下界。     

混合图的双向连通定向

无向图的双向连通定向对单行道路系统的构造有着重要意义。本文讨论的问题实际上是无向图的双向连通定向问题的一种推广。本文主要结果有:1.设 B 为混合图 M 的任一 k-断集,则 M 有双向连通定向的充要条件为 M 是混合连通且 k≥2。2.设图 M 有混合 Euler-迹,又 M 中任一断集 B 有|B|≥2k,则 M 有一个 k-弧连通定向。3.设无环图 M 为混台连通,又 b∈E(M)∪A(M),有 M-b 为混合连通,则 M 的 DFS-图是双向连通。     

混合图的双向连通定向

无向图的双向连通定向对单行道路系统的构造有着重要意义。本文讨论的问题实际上是无向图的双向连通定向问题的一种推广。本文主要结果有:1.设 B 为混合图 M 的任一 k-断集,则 M 有双向连通定向的充要条件为 M 是混合连通且 k≥2。2.设图 M 有混合 Euler-迹,又 M 中任一断集 B 有|B|≥2k,则 M 有一个 k-弧连通定向。3.设无环图 M 为混合连通,又(?)b∈E(M)∪A(M),有 M-b 为混合连通,则 M 的 DFS-图是双向连通。