论文部分内容阅读
图谱理论的研究主要是利用成熟的代数理论和技巧,利用矩阵的特征值的性质,并结合图论和组合数学的理论来研究图谱、图的结构性质以及与图的其它不变量之间的关系.它是代数图论中的一个重要研究课题,在理论化学、物理学、通讯网络、信息科学等领域中都有重要应用在本文中,主要研究了强连通有向图的邻接谱、图的拉普拉斯Estrada指数、图的无符号拉普拉斯特征值前k大之和的上界以及正则图的变换图的无符号拉普拉斯矩阵的特征多项式. 强连通有向图是指任意两个顶点之间都有有向路相连的有向图.当n≥4时.我们确定了n阶强连通有向图中谱半径第二小,第三小和第四小的图,解决了Lin和Shu在[H.Lin,J.Shu,A note on the spectral characterization of strongly connectedbicyclic digraphs,Linear Algebra Appl.436(2012)2524-2530]中提出的公开问题.同时,我们也确定了在有向强连通双圈图中谱半径第二小,第三小的图以及谱半径第二大的图. 图G的拉普拉斯Estrada指数定义为LEE(G)=n∑i=1eμi,其中μ1≥μ2≥…≥μn是图G的拉普拉斯特征值.在(n,m)图中,我们证明了LEE(G)≤([)2m/n」en+n-([)2m/n」-1+e2m-n([)2m/n」,且等号成立当且仅当G≌Kn或G≌Kn-e,而当n≥7,n≤m≤3n-7/2时,LEE(G)≤en+em-n+3+(m-n)e2+(2n-m-3)e+1,且等号成立当且仅当G≌K1∨(Sm-n+2∪(2n-m-3)K1).此外,我们也证明了给定点数n和色数x(x≥2)的图中,当x≤n<2x时,LEE(G)≤(x-1)en+(n-x)en-2+(2x-2)en-1+1,且等号成立当且仅当G≌Tn,x,当2x≤n≤2x+3且n≠7.x≠2时,LEE(G)≤(x-1)en+2(n-2x)en-3+(3x-n)en-2+1,且等号成立当且仅当G≌Tn,x,而当n≥2x+4或n=7,x=2时,LEE(G)≤(x-1)(en+en-2)+(n-2x+1)e2x-2+1,且等号成立当且仅当G≌Kn-2x+2,2…,2.(})x-1 设图G的无符号拉普拉斯特征值为q1≥q2≥…≥qn,k是一个正整数.且1≤k≤n,S*k(G)=k∑i=1 qi,e(G)=|E(G)|.Ashraf等提出猜想,即S*k(G)≤e(G)+(k+12).并证明了该猜想当k=2时对所有图以及正则图时对所有k都成立.对连通图G,当k充分大,或当1≤k≤n,G是树,单圈图(除一个图且k=2外),双圈图时,我们给出了一个更好的上界,即S*k(G)≤e(G)+(k+12)-2k-2/n. xyz-变换图的邻接矩阵多项式以及拉普拉斯多项式,有向变换图的邻接矩阵多项式都得到了充分的研究.对n个顶点,m条边的r-正则图G,我们用n,m,r以及图G的无符号拉普拉斯谱表达出其xyz-变换图Gxyz(x,y,z∈{0,1,+,-})的无符号拉普拉斯多项式.