一些极值图问题的谱条件综述（英文）

这篇综述分为两个方面.首先,我们总结了图论中的Turan型问题的谱极值结论的最新进展.更准确地说,关于各种图的邻接谱半径和无符号拉普拉斯谱半径,我们总结了它们的谱版本的Turán型函数.例如,完全图、色数至少为3的一般图、完全二部图、奇圈、偶圈、色临界图和相交三角形图.第二个目标是总结一些最近的关于图性质的谱条件.通过一种统一的方法,基于邻接谱半径和无符号拉普拉斯谱半径,我们给出了一些充分条件,使得该图成为哈密顿图、k-哈密顿图、k-边哈密顿图、可迹图、k-路径可覆盖图、k-连通图、k-边连通图、哈密顿连通图、完美匹配图和β-亏量图.     

哈密顿连通图和可迹图的新充分谱条件

令G是一个简单连通图,ρ(G)和q~D(G)分别为图G的邻接谱半径和距离无符号拉普拉斯谱半径.提供了图G是哈密顿连通的两个新的谱充分条件,这两个充分条件分别是以ρ(G)和q~D(G)表示的,其中G是G的补图.进一步地,还给出了以q~D(G)表示的图G是从任意一点出发都是可迹的新的谱充分条件,从而扩展和改进了文献中的结果.     

双圈图的距离无符号拉普拉斯谱半径

连通图$G$的距离无符号拉普拉斯矩阵定义为$\mathcal{Q}(G)=Tr(G)+D(G)$, 其中$Tr(G)$和$D(G)$分别为连通图$G$的点传输矩阵和距离矩阵. 图$G$的距离无符号拉普拉斯矩阵的最大特征值称为$G$的距离无符号拉普拉斯谱半径. 本文确定了给定点数的双圈图中具有最大的距离无符号拉普拉斯谱半径的图.     

连通图的谱半径上界

图谱理论是图论研究的重要的领域之一.设图G是n阶简单连通图,具有n顶点和m条边的连通图,p(G)为图G的邻接矩阵的谱半径.利用代数的方法得出两个ρ(G)的上界为:■与■和达到上界的图.     

可迹图的谱充分条件

设G是一个简单图,A(G),Q(G)以及Q(G)分别为G的邻接矩阵,无符号拉普拉斯矩阵以及距离无符号拉普拉斯矩阵,其最大特征值分别称为G的谱半径,无符号拉普拉斯谱半径以及距离无符号拉普拉斯谱半径.如果图G中有一条包含G中所有顶点的路,则称这条路为哈密顿路;如果图G含有哈密顿路,则称G为可迹图;如果图G含有从任意一点出发的哈密顿路,则称G从任意一点出发都是可迹的.主要研究利用图G的谱半径,无符号拉普拉斯谱半径,以及距离无符号拉普拉斯谱半径,分别给出图G从任意一点出发都是可迹的充分条件.     

不含三圈的k圈图的拟拉普拉斯和拉普拉斯谱半径

k圈图是边数等于顶点数加k-1的简单连通图.文中确定了不含三圈的k圈图的拟拉普拉斯谱半径的上界,并刻画了达到该上界的极图.此外,文中确定了拟拉普拉斯谱半径排在前五位的不含三圈的单圈图,排在前八位的不含三圈的双圈图.最后说明文中所得结论对不含三圈的k圈图的拉普拉斯谱半径也成立.     

关于连通度固定的图的拉普拉斯谱半径的一个注记(英文)

图的拉普拉斯谱半径是其拉普拉斯矩阵的最大特征值.本文刻画了(边)连通度至多为k的二部图中具有最大拉普拉斯谱半径的所有图.[Linear Algebra Appl.,2009,431(1):99-103]也考虑了此问题,而所得到的结果并不完整.     

图的路径与半边路径之间的一种关系

本文主要研究了连通图的半边路径数目和两个辅助图的路径数目之间的一种关系.并且根据这种关系,我们给出了连通图和平面图的无符号拉普拉斯谱半径的一些上界.     

给定最大度的单圈偶图的谱半径

单圈偶图是边数等于顶点数的简单连通偶图.Δ（G）表示图G的最大度.文中给出了最大度为Δ(≥ⁿ⁺¹/2)的n阶单圈偶图的谱半径的上界,并刻画了达到该上界的图.文中还证明了当Δ（G）≥[（2n+1）/3]+1时,n（≥8）阶单圈偶图G的谱半径随着最大度的递增而严格递增,并在此基础上给出了谱半径排在前17位的n（≥16）阶单圈偶图.     

关于双圈图的谱半径

如果G是连通的并且G的边数是n 1,那么n阶图G叫做双圈图,设B(n)是所有的阶为n的双圈图构成的集合,本文给出了B(n)(n(?)9)中前三大的邻接谱半径以及它们对应的图.