具有n-3个悬挂点的单圈图补图的最小特征值

特征值的极图问题一直是谱图理论的研究热点,与谱半径相比,最小特征值的研究较少,但图的最小特征值同样能较好地反映图的结构信息,具有很强的研究价值。本文主要讨论给定阶数n且悬挂点为n-3的单圈图补图图类中邻接矩阵的最小特征值,刻画了最小特征值达极小的唯一图。     

自补图的独立数与覆盖数

主要讨论了自补图的边独立数和边覆盖数,给出了点独立数的严格上、下界： ,其中 是 的点色数,分析并证明了点独立数取得上、下界的自补图的存在性。     

具有n-4个悬挂点的三圈图补图的最小特征值

为了讨论给定阶数为n且具有n-4个悬挂点的三圈图补图图类中邻接矩阵的最小特征值,刻画其最小特征值达到极小的唯一图。在只考虑简单无向连通图的基础上,从补图的结构出发研究图的最小特征值,通过运用相关知识点分析论证了当值为λ(G(■(n-4)/2?,?(n-4)/2■)~C)时,给定阶数为n且具有n-4个悬挂点的三圈图补图图类中邻接矩阵的最小特征值达到极小的唯一图。结果表明:结合图邻接矩阵是表示顶点之间相邻关系的矩阵,它的最小特征值为图的最小特征值,较好地刻画图的本质性质。研究得出的具有n-4个悬挂点的三圈图补图的最小特征值达到极小的唯一图,为后续进一步研究补图图类中邻接矩阵的最小特征值提供了一定的借鉴价值。     

仅有三个悬挂点的图的补图的最小特征值

设图G是点集为V(G)＝{v1,v2,…,vn}的简单连通图,则G的邻接矩阵是A(G)＝(aij)n×n,其中若vi和vj相邻,则aij＝1,否则aij＝0.由于A(G)是实对称的,因此可将其特征值设为λ1(G)≥λ2(G)≥…≥λn(G),且A(G)的特征值也称为G的特征值.该文在仅有三个悬挂点的图的所有连通补图中,确定了其最小特征值达到最小值时的唯一图.     

最小Q-特征值为给定整数的一类图

研究了基于二部图H构造的一类图的最小无符号拉普拉斯特征值,即最小Q-特征值,得到了它的最小Q-特征值的可达上界为1.给出了最小Q-特征值为1的2个必要条件,并构造了最小Q-特征值为1的一类图.另外,给出了利用H∨K1的最小Q-特征值来判断简单图H没有完美匹配的方法,以及图G增加边后最小Q-特征值保持不变的1个充分条件.最后,构造了最小Q-特征值为任意给定的正整数t的一类图.     

含一个割点的连通图的最小特征值

一个图的无符号拉普拉斯最小特征值在某个图类中的所有图中达到最大时常称为极大图;通过利用特征向量方程研究特征值的方法,对只含有一个割点的连通图的无符号拉普拉斯最小特征值进行了研究,且得到了最小特征值的值,从而得到了只含有一个割点的具有相同阶数的所有的连通图中最小特征值的极大值,并且刻画了最小特征值取到极大值时所对应的极大图的结构.     

支配数为1的图的最小特征值

本文中主要刻画了给定阶数且支配数为1的图类中最小特征值达到极小的图的结构。     

一类特殊图的最小特征值

图的邻接矩阵是表示顶点之间相邻关系的矩阵,它的最小特征值被定义为图的最小特征值,图的最小特征值是解析图的结构性质的重要概念。本文讨论了一类特殊图类的最小特征值,并刻画了此类图最小特征值达极小的唯一图。     

图与其补图的独立数之间的关系

文章讨论了图G及其补图(?)的独立数之间的关系,得到的主要结果是a(G) a((?))(?)n 1.     

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

设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为正则图。     

独立点数为2的图的Z_3-连通性

设G是独立点数为2的连通简单图.主要证明两个结论:(1)当边连通为4时,G是Z_3-连通的;(2)当点连通为3时,G是Z_3-连通的当且仅当G■{K_4,W_5}且G不是一类特殊的图.     

几类图的独立约束数及独立加强数

利用归纳假设方法及图的独立数的一些定理，研究几类图——路、完全二分图、圈、树中的独立约束数及独立加强数．求出路、圈的独立约束数和独立加强数及完全二分图的独立约束数，并给出树独立加强数的界．     

独立点数为3的图的Z3-连通性

Jaeger猜想为"5-边连通图是Z3-连通的",此猜想对于独立点数为2的图是成立的.利用收缩、点分裂、反证等方法,证明了此猜想对于独立点数为3且点连通度不大于5的图也是成立的.     

积图的独立数和上无赘数

证明任意两个图G和H的积图G×H的独立数不小于这两个图的独立数之积,即β(G×H)≥β(G)×β(H);任意两个图G和H的积图G×H的上无赘数不小于这两个图的上无赘数之积,即IR(G×H)≥IR(G)×IR(H).     

变换图G~(*xy)的独立数

变换图的概念由全图推广而来。文章在中图的补图M(G)的定义启发下,定义了四类变换图,其中一个恰是(G),并探讨了这些变换图的独立数。研究了变换图G*-+的独立数与原图最大度的关系,以及G*++与G*+-的独立数与原图边独立数的关系。     

最小度至少是5的图的控制数

设G是n个顶点的简单图．运用Reed引进的顶点不交的路覆盖,找出函G的一个控制集并估算这个控制集的基数’结合估算结果,证明如果图G的最小度至少是5,则图G有基数至多是击n的控制集.     

双圈图的优美性

针对双圈图, 设计一种图的优美性判定算法, 并对17个点内的所有双圈图进行优美性验证, 得到了该范围内所有的优美图和非优美图. 结果表明, 在17个顶点范围内, 除∞ 型双圈图C_(m,n)外, 其余所有双圈图都是优美的, 其中(m+n)(mod 4)={1,2}. 最后给出该类图的非优美证明, 并进一步猜测当顶点数大于17时, 该结论仍成立.     

具有最小Wiener指数的双圈图

一个图G的Wiener指数W(G)定义为G中所有点对的距离和,双圈图是一个具有n个点和n+1条边的连通图,我们根据两个圈的相对位置关系把双圈图分成三类,分别在这三类中给出了最小的Wiener指数,然后通过比较三类极值的大小得到了双圈图中具有最小Wiener指数的图。     

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

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