图的谱半径与拟悬挂点数

设G(n,k)为含有k个拟悬挂点的n阶图所构成的集合.本文刻画了在G(n,k)中无符号Laplace谱半径达到最大的图,同时给出了当k=0,1,2,3时,在G(n,k)中无符号Laplace谱半径达到最小的图.     

给定染色数的无符号Laplace谱半径

设Gkn(k≥2)为n阶的染色数为k的连通图的集合.本文确定了Gkn中具有极大无符号Laplace谱半径的图,即k=2时为完全二部图,k≥3时为Turn图.本文也讨论了Gkn中的具有极小无符号Laplace谱半径的图,对k≤3的情形给出了此类图的刻画.     

c-圈图的Laplace谱半径和最大度

设G是一个n阶的简单连通图,符号(d_1,d_2,...,d_n)表示G的度序列,其中d_1≥d_2≥···≥d_n,用符号?(G)表示G的最大度,而符号λ(G)表示G的Laplace谱半径.一个c-圈图是一个恰有n+c-1条边的n阶简单连通图,而符号C(n,?;c)表示最大度等于?的所有n阶c-圈图的集合.本文确定了当0≤c≤1/2(?-1)(?-2)时,C(n,?;c)中所有取得最小Laplace谱半径的极图,并分别确定了当?≥[n+2/3]且d_4≥2或?≥[n/3]+1且d_4=1时,C(n,?;1)中唯一取得最大Laplace谱半径的极图.进一步地,还证明了对于两个n阶的单圈图G和G′,如果?(G)≥[11n/30]+2且?(G)?(G′),则λ(G)λ(G′),并且界"[11n/30]+2"是最佳的.     

连通图的最小Laplace谱半径的排序

首先找出了具有最小Laplace谱半径的第2个至第5个n阶单圈图和具有最小Laplace谱半径的n阶双圈图.然后结合有关n阶树的最小Laplace谱半径的排序,给出了所有n阶连通图中Laplace谱半径最小的14个图,当n为偶数时,它们达到了所有佗阶连通图中Laplace谱半径最小的9个值(其中有并列的),而当n为奇数时,它们则达到了Laplace谱半径最小的8个值(其中有并列的).     

可迹图的谱充分条件

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

三圈图的无符号拉普拉斯谱半径

假设图G的点集是V(G)={v_1,v_2,…,v_n},用d_(v_i)(G)表示图G中点v_i的度,令A(G)表示G的邻接矩阵,D(G)是对角线上元素等于d_(v_i)(G)的n×n对角矩阵,Q(G)=D(G)+A(G)是G的无符号拉普拉斯矩阵,Q(G)的最大特征值是G的无符号拉普拉斯谱半径.现确定了所有点数为n的三圈图中无符号拉普拉斯谱半径最大的图的结构.     

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

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

k-边连通图的新充分谱条件

令G是一个简单连通图.如果连通图G被删除少于k条边后仍然保持连通,则称G是k-边连通的.基于图G或补图■的距离谱半径,距离无符号拉普拉斯谱半径,Wiener指数和Harary指数,提供了图G是k-边连通的新充分谱条件,从而建立了图的代数性质与结构性质之间的紧密联系.     

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

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

具有k个悬挂点的n阶单圈图的第二大谱半径的极图

设G为具有k个悬挂点的n阶单圈图,刘慧清等给出了这类图的最大谱半径的极图,本文得到了当k≥3时具有第二大谱半径的极图.     

图的符号星k控制数

引入了图的符号星k控制的概念.设G=（V,E）是一个图,一个函数f：E→{-1,＋1},如果∑e∈E[v]f（e）≥1对于至少k个顶点v∈V（G）成立,则称f为图G的一个符号星k控制函数,其中E（v）表示G中与v点相关联的边集.图G的符号星k控制数定义为γkss（G）=min{∑e∈Ef（e）｜f为图G的符号星k控制函数}.在本文中,我们主要给出了一般图的符号星k控制数的若干下界,推广了关于符号星控制的一个结果,并确定路和圈的符号星k控制数.     

单圈混合图的极大谱半径

设U＊为一个未定向的n个顶点上的单圈混合图，它是由一个三角形在其某个顶点上附加”一3个悬挂边而获得．在文[Largest eigenvalue of aunicyclic mixed graph，Applied Mathematics A Journal of Chinese Universities （Ser．B），2004，19（2）：140-J48]中，作者证明了：在相差符号同构意下，在所有n个顶点上的单圈混合图中，U＊是唯一的达到最大Laplace谱半径的混合图．本文应用非负矩阵的Perron向量，给出上述结论的一个简单的证明．     

单圈图与双圈图补图的Aα-谱半径

设A(G)和D(G)分别表示n阶图G的邻接矩阵和度对角矩阵,对于任意实数α∈[0,1],图G的Aα-矩阵被定义为Aα(G)=αD(G)+(1?α)A(G),它是图的邻接矩阵和无符号拉普拉斯矩阵的共同推广,其最大特征根称为图G的Aα-谱半径.单圈图与双圈图补图的Aα-谱半径的上界被分别确定,相应的极图被完全刻画.     

利用计算机计算n阶图的特征多项式的方法

1引言设G=（V,E）为n阶无向的简单连通图.记N（v）为v的所有相邻点的集合,则d（v）=|N（v）|称为顶点v的度.若d（v）=1,则称v为G的一个悬挂点.设D（G）=diag（d（v₁）,d（v₂）,…,d（v_n））和A（G）分别表示图G的度对角矩阵和邻接矩阵,则L（G）=D（G）-A（G）称为图G的Laplace矩阵,而Q（G）=D（G）+A（G）称为图G的SignlessLaplace矩阵.用符号N_m×n表示一个m行n列的矩阵,M_n表示一个n阶的方阵.特     

双圈图的Laplace矩阵的谱半径

利用奇异点对的分类,得到了n阶双圈图的Laplace矩阵的谱半径的第二至第八大值,并且刻划了达到这些上界的极图.     

单圈图与双圈图补图的A_(a~-)谱半径

设A(G)和D(G)分别表示n阶图G的邻接矩阵和度对角矩阵,对于任意实数α∈[0, 1],图G的A_(a~-)矩阵被定义为Aα(G)=αD(G)+(1-α)A(G),它是图的邻接矩阵和无符号拉普拉斯矩阵的共同推广,其最大特征根称为图G的A_(a~-)谱半径.单圈图与双圈图补图的A_(a~-)谱半径的上界被分别确定,相应的极图被完全刻画.     

强连通双圈有向图的无符号拉普拉斯谱刻画

设$\overrightarrow{G}$ 是一个强连通双圈有向图, $A(\overrightarrow{G})$是其邻接矩阵.设$D(\overrightarrow{G})$ 是$\overrightarrow{G}$的顶点出度的对角矩阵, $Q(\overrightarrow{G})=D(\overrightarrow{G})+A(\overrightarrow{G})$是$\overrightarrow{G}$ 的无符号拉普拉斯矩阵. $Q(\overrightarrow{G})$的谱半径称为$\overrightarrow{G}$的无符号拉普拉斯谱半径.在这篇文章中, 确定了在所有强连通双圈有向图中达到最大或最小无符号拉普拉斯谱半径的唯一有向图. 此外,还证明了任意一个强连通双圈有向图是由它的无符号拉普拉斯谱所确定的.     

Laplace特征值的一点注记

确定具有n个顶点e条边的图的Laplace的最大谱半径.     

图的规范拉普拉斯特征值的上界（英文）

设G为具有n个顶点的简单连通图.本文给出了图G的第k大规范拉普拉斯特征值的两个新上界,分别推广了已有的规范拉普拉斯谱半径的两个上界.     

恰有k个悬挂点的n阶双圈和三圈图的拟拉普拉斯谱半径

设k,n为两个确定的正整数.本文得到了当1≤k≤n-7时恰有k个悬挂点的n阶连通三圈图的最大拟拉普拉斯谱半径的唯一极图,也得到了当1≤k≤n-5时恰有k个悬挂点的n阶连通双圈图的最大拟拉普拉斯谱半径的唯一极图.