非二部图的最小特征值

设G是一个简单图,其特征值定义为它的邻接矩阵的特征值。在给定阶数的非二部图中,本文确定了最小特征值达到极小的图,并在文末提出一个问题及相关的猜想。     

直径为3的图的最小特征值

设Y是一个图集合,若对于Y中的所有图中,图G的最小特征值可以达到最小,则称G是集合Y中最小特征值的极小图。本文刻画了直径为3的n阶连通图最小特征值及其极小图。     

最小Q-特征值第二小的给定悬挂点数的非二部单圈图

图的最小Q-特征值常被用来衡量一个图的非二部程度,受到研究者的广泛关注。在路Pn-k-2的一端接出一个圈C3,另一端接出k个悬挂边,所得的n阶图记为Ukn(3)。范益政等人最近证明Ukn(3)是最小Q-特征值达到最小的图。在他们的基础上,证明C13(n-k-1)是最小Q-特征值达到第二小的图,其中C13(n-k-1)是将Ukn(3)的一条悬挂边移至与悬挂邻点相邻的非悬挂点上所得的图。     

赋权图中第二大特征值和最小特征值的界

运用ｎ阶非负矩阵Ｂ＝（ｂｉｊ）≥０的第二大特征值的界的结果,研究了ｎ阶赋权图Ｇ的邻接矩阵在行和相等时最大特征值的值和第二大特征值θ２（Ａ（Ｇ））以及最小的特征值θｎ（Ａ（Ｇ））的界．     

图的第四大Q-特征值简

主要研究图的Q-特征值,刻画了第四大Q-特征值不超过1的连通图,并且得到了关于此性质的所有禁用子图.     

一类非奇异混合图的特征值分布

设G是一个连通的含圈C6至少9个顶的非奇异二部混合图。根据简单图的特征值分布与匹配及其子图的关系,确定了至多有三个特征值大于2的上述图G。     

图的第二个最小特征值的界

设Ｇ是ｎ个顶点的简单图，λｎ－１（Ｇ）为Ｇ的第二个最小特征值。Ｇ的非孤立点形成的图记为Ｇ１，Ｖ（Ｇ１）＝ｓ，（３≤ｓ≤ｎ）。本文主要证明了：ａ．若Ｇ１不是完全偶图，则λｎ－１（Ｇ）≤λｓ－１（Ｋ２，ｓ－２＾－ｅ），等式成立＝Ｇ１≌Ｋ２，ｓ－２＾－＾ｅ。其中图Ｋ２，ｓ－２＾－＾ｅ为完全偶图Ｋ２，ｓ－２去掉一边ｅ而得到的图ｂ．若Ｇ１既不是完全偶图，又不是Ｋ２，ｓ－２＾－ｅ，则λｎ－１（Ｇ）＜－√２／２     

一类特殊图的最小特征值

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

图的第二个最小特征值的界

设 G 是 n 个顶点的简单图,λ_(n-1)(G)为 G 的第二个最小特征值。G 的非孤立点形成的图记为 G_1,V(G_1)=s,(3≤s≤n)。本文主要证明了:a.若 G_1不是完全偶图,则λ_(n-1)(G)≤λ_(s-1)(K_(2,s-2)-(?)),等式成立(?)G_1(?)K_(2,s-2)-e。其中图 K_(2,s-2)-e 为完全偶图 K_(2,s-2)去掉一边 e而得到的图 b.若 G_1既不是完全偶图.又不是 K_(2,s-2)-e,则λ_(n-1)(G)<-2~(1/2)/2。     

k-正则图中第二大特征值和最小特征值的界

运用n阶矩阵B=(b_(ij))≥0的第二大特征值的结果,结合图论的背景,得出了n阶k-正则图G的第二大特征值θ_2(A(G))≤k-(?){|N_i∩N_j|},最小的特征值θ_n(A(G))满足:θ_n(A(G))≥-1-(?){k-|N_i∩N_j|-1,k- |N_i∩N_j| 1}.     

Split完全图的最小直径定向

利用n 部完全图定向问题的结论,研究一类特殊图——split完全图的最小直径的定向问题,得到split完全图满足2 直径定向的条件及构作.     

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

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

单圈图依次小Q-特征值排序

n阶图G叫做单圈图,如果G是连通的,并且G的边数也是n.图G的无符号拉普拉斯矩阵定义为Q(G)=D(G)+A(G),其中D(G)是以G所有顶点的度为对角元的对角阵,A(G)是图G的邻接矩阵.Q(G)是一个实对称的半正定矩阵,设它的特征值为q1(G)≥q2(G)≥…≥qn(G)≥0.图G的依次小Q-特征值为qn-1(G),简记为k(G).主要研究单圈图的k(G),记阶数为n的所有连通的单圈图的集合为U(n),给出了当阶数n≥25时,U(n)中依次小Q-特征值为前3大的图.     

S-系包含图

设S是一个半群,M是S-系。M的包含图记为G(M),G(M)是无向简单图,它的顶点集由M的非平凡子系构成,顶点集中任意不同的两点是连接的当且仅当其中一个非平凡子系包含在另一个非平凡子系之中。基于该定义对这类图的完全性、连通性、直径、围长、团数和色数等性质进行了研究。     

完全偶图的定向图

完全偶图是具有二分类（X,Y）的简单偶图,其中X的每个顶点与Y的每个顶点相连,若｜X｜=m,｜Y｜=n,则这样的图记为K_m,n。本文主要研究了Kn,n的定向图。证明了如下结论：对于非负整数a和b,若存在满足每个顶点的入度是a或者是b的一个Kn,n的定向图,则存在非负整数s和t满足方程s+t=2n和as+bt=n2。进一步,对于满足特定条件的非负整数a,b和n,存在K_n,n的定向图使得每个顶点的入度非a即b。     

最大外可平面图的树图

通过对最大外可平面图和Ｋ临界图的研究给出三个主要结论（１）最大外可平面图的生成树有２＾ｐ－３＊３棵。（２）最大外可平面图的树图ＧＴ,β（ＴＧ）≥ｐ＋１。（３）临界图Ｇ,当Ｋ（Ｇ）＝１时,树图ＧＴ是平凡图,当Ｋ（Ｇ）＝２时,对图ＧＴ是ｐ图。     

蛛形图的全图和中心图的均匀染色

通过研究蛛形图的全图和中心图的性质,给出具体的独立集分法,得到了蛛形图G删去头点后有n条长为n-1的路.把图G的全图记为T(G),则G的全图的均匀色数χ{Eq}[T(G)]=n+1.把 G 的中心图记为{C(G)},也得到了这样的蛛形图G的中心图的均匀色数:当 n=2k时,χ{Eq}[C(G)]=2k2+1;当n=2k+1时,{χ{Eq}[C(G)]=}2k2+3k+1.     

三次图的完全扩容图的连通度

目的研究三次图的完全扩容图的连通度。方法利用反证法。结果与结论3-连通三次图的完全扩容图也是3-连通三次图。