剖分点一边冠图的电阻距离和Kirchhoff指标（英文）

图G的剖分图S(G)是在图G的每条边上加一个顶点.这些新添加的点的集合称为I(G).在三个图G_1,G_2和G_3的基础上引进了一种新的图运算,称为剖分点一边冠图,记作G_1~So(G_2~V∪G_3~E),它由S(G_1),|V(G_1|个G_2的拷贝和|I(G_1|个G_3的拷贝组成,将V(G_1)中的第i个顶点和第i个G_2的拷贝中的每个顶点连接,同时将I(G1)中的第i个顶点和第i个G_3的拷贝中的每个顶点连接.本文给出了剖分点一边冠图的电阻距离和Kirchhoff指标.     

局部剖分邻接冠图的谱（英文）

设G_1,G_2是两个简单连通图,图G_1,G_2的局部剖分邻接冠图G_1■G_2是指复制一个G_1和|V(G_1)|个G_2,图G_1的第i个点的邻点与复制的第i个图G2的每一个点相连接,然后在G_1每一条边上插入一个新的点而得到的图类.本文利用两个图G_1,G_2的邻接谱、Laplacian谱和无符号Laplacian谱刻画了局部剖分邻接冠图G_1■G_2的邻接谱、Laplacian谱和无符号Laplacian谱.另外,本文利用上述结果构造出了若干对邻接同谱图、Laplacian同谱图和无符号Laplacian同谱图.进一步地,本文也利用两个因子图G_1,G_2的Laplacian谱计算出了局部剖分邻接冠图G_1■G_2的生成树数目.     

基于拉普拉斯谱确定的两类树

设图G是简单连通图.如果任何一个与图G关于拉普拉斯矩阵同谱的图,都与图G同构,称图G可由其拉普拉斯谱确定.定义了树Y_n和树F(2,n,1)两类特殊结构的树.利用同谱图线图的特点,证明了树Y_n和树F(2,n,1)可由其拉普拉斯谱确定.     

冠图(G_1○G_2)○G_3的Wiener指数

给出了冠图(G_1·G_2)·G_3的Wiener指数W((G_1·G_2)·G_3),得出了W((G_1·G_2)·G_3)与三个图的边数和顶点数有关,且与G_1的结构有关,而与G_2、G_3的结构无关.     

含偶圈图的Laplacian 谱刻画

设 H(K_{1,5},P_n,C_l)是由路 P_n的两个悬挂点分别粘上星图K_{1,5}的悬挂点和圈 C_l的点所得的单圈图. 若两个二部图是关于Laplacian 矩阵同谱的, 则它们的线图是邻接同谱的, 两个邻接同谱图含有相同数目的同长闭回路. 如果任何一个与图G关于Laplacian 同谱图都与图G 同构, 那么称图G可由其Laplacian 谱确定. 利用图与线图之间的关系证明了H(K_{1,5},P_n,C_4)、H(K_{1,5},P_n,C_6) 由它们的Laplacian谱确定.     

几类多圈图的拉普拉斯谱刻画

设图G是一个简单连通图. 如果任何一个与图G同拉普拉斯谱的图都与图G同构,则称图G是由其拉普拉斯谱确定的. 定义了双圈图\theta_{n}(p_1,p_2,\cdots,p_t) 和m 圈图H_n(m\cdot C_3;p_1,p_2,\cdots,p_t). 证明了双圈图\theta_{n}(p)和\theta_{n}(p,q),三圈图H_n(3\cdot C_3;p)和H_n(3\cdot C_3;p,q)分别是由它们的拉普拉斯谱确定的.     

一些双联运算图的规范拉普拉斯谱

研究了基于剖分图、Q-图、R-图和全图的双联运算图的四类变型,给出了它们的规范拉普拉斯谱.所得结果推广了关于图的联运算的一些已有结果.     

F型树F(m,n)可由其Laplacian谱唯一确定

讨论了“哪些图由它的Laplacian谱确定？”的问题，一棵树称为F型树，如果其由一梳图的一个2度顶点与一条路的悬挂点邻接而成。本文利用同谱图的线图的特点，证明了，型树可由它的Laplacian谱确定。     

关于拉普拉斯谱半径的一个不等式

设G是一个简单连通图,v是图G的一个割点.G_1,G_2,…,G_s(s≥2)是图G的s个v-分支.令H_1=G_1∪G_2∪…∪G_t,H_2=G_(t+1)∪G_(t+2)∪…∪G_s,其中1≤t相似文献   

关于边数给定图按无符号拉普拉斯谱半径排序的注记

设$k$是正整数, $G$是一个边数给定的简单无向图, 其边数$m\ge 2k$, 最大度$\Delta(G)\le m-k$, 本文给出了图$G$的无符号拉普拉斯谱半径$q(G)$的一个上界. 对边数为$m\ge 8$的两个连通图$G_1$和$G_2$, 利用这个上界我们证明了一个排序定理: 如果$\Delta(G_1)>\Delta(G_2)+1$ 且 $\Delta(G_1)\ge \frac{m}{2}+2$, 那么$q(G_1)>q(G_2)$. 对于不含三角形的图, 我们得到两个更强的结果. 作为上述排序定理的一个应用, 我们完全刻画了无符号拉普拉斯谱半径最大的围长为$c$的$m$边图, 其中$m\ge \max\{ 2c, c+9\}$, 部分解决了陈雯雯等人在[Linear Algebra Appl. 645(2022)123-136]上提出的一个公开问题.     

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

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

关于交叉数为2的联图

确定图的交叉数是NP-完全问题.Kuratowski定理刻画了平面图的结构特征,而对于交叉数为k(k≥1)的非平面图G的结构特征刻画,目前相关结果甚少.对于交叉数为1的联图G_1∨G_2,我们已经刻画出因子图G_1和G_2满足的充要条件.本文刻画了当△(G_2)≠3且cr(G_1∨G_2)=2时因子图G_1和G_2须满足的充要条件.     

若干图的卡氏积的距离谱和距离能量(英文)

G是顶点集为{v_1,v_2,…,v_n}的连通简单图,G_1,G_2,…,G_n是有限图。联并图G[G_1,G_2,…,G_n】是按如下方式在G_1UG_2U…UG_n上加边而成的图:在G_i和G_j之间的任何两个顶点间加边,若v_i和v_j在G中相邻.[7]给出了两个距离正则图的卡氏积的距离谱.本文计算了联并图和距离正则图的卡氏积及两个联并图的卡氏积的距离谱.在此基础之上,我们得到了两个利用联并图与非同谱距离正则等能量图作卡氏积及联并图作卡氏积构造非同谱等距离能量图族的方法.     

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

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

图类■中的整谱图

设图G是一个简单图,图G的补图记为-G,如果G的谱都是整数,就称G是整谱图.鸡尾酒会图CP(n)=K2n-nK2(K2n是2n阶完全图)和完全图Ka都是整谱图[1].本文确定了图类■中的所有整谱图.     

图类￣(αKa∪βCP(b))中的整谱图

设图G是一个简单图,图G的补图记为(G),如果G的谱都是整数,就称G是整谱图.鸡尾酒会图CP(n)=K2n-nK2(K2n是2n阶完全图)和完全图Ka都是整谱图[1].本文确定了图类￣αKa∪βCP(b)中的所有整谱图.     

几类特殊Corona图的b-染色数与b-连续性研究

在一个图G的正常k染色中,如果每一个颜色类中都至少存在一个顶点,使得其在其它的k-1个颜色类中都至少有一个邻居,则称这样的正常k染色为b-染色.一个图G的b-染色数是最大的正整数k,使得用k种颜色能够对G进行b-染色,用b(G)来表示.如果对于任意的正整数k:χ(G)≤k≤b(G),用k种颜色可以对图G进行b-染色,则称图G是b-连续的.设G1与G2为任意图,称图G=G_1·G_2为图G_1与G_2的Corona图,其中G包含G_1的一个拷贝,包含G_2的|V(G_1)|个拷贝,且G_1的第i个顶点与G_2的第i个拷贝的所有顶点都邻接.研究了路图与路图、星形图以及轮图所构成的Corona图P_n·P_m、P_n·K_(1,m)以及P_n·W_(m+1)的m-度,b-染色数与b-连续性.     

直径为n-4的图的最小无号拉普拉斯谱半径

Liu Lu和Shu等在[The minimal Lapacian spectral radius of trees with a given diameter,Theoretical Computer Science,2009,410:78-83]中分别给出了直径为{1,2,3,4,n-3,n-2,n-1}的具有最小拉普拉斯谱半径的树.本文给出了直径为n-4的具有最小无号拉普拉斯谱半径的图.作为推论,给出了直径为n-4的具有最小拉普拉斯谱半径的村.     

图经广义并接运算后的(无符号拉普拉斯)特征值的一些结论（英文）

设G是一个顶点集为{u_1,u_2,…,u_n}的点标号图,H_1,H_2,…,H_n是n个顶点不交的图,将图G中的顶点u_i(i=1,2,…,n)用图H_i代替,若点u_i与点u_j在G中相邻,则连接H_i与H_j中的所有的点,这样得到的图定义为G[H_1,H_2,…,H_n].本文确定了图G[H_1,H_2,…,H_n]的Q-特征多项式和A-特征多项式.最后,作为应用,构造了很多对(无符号拉普拉斯)-同谱图,并给出了一些关于特殊图类的Q-特征值和A-特征值的不等式序列.     

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

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