剖分点—边冠图的谱(英文)

在三个图G_1,G_2和G_3的基础上引进了一种新的图运算,在这种运算下得到的图称为剖分点一边冠图,记作G_1~S·(G_2~V∪G_3~E).同时,当G_1是正则图时,确定了剖分点一边冠图的邻接谱和拉普拉斯谱.作为应用,构造了无穷多对邻接同谱图和拉普拉斯同谱图.此外,还确定了剖分点一边冠图的生成树的个数.     

含偶圈图的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谱确定.     

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

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

剖分点一边冠图的电阻距离和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指标.     

几类特殊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-连续性.     

几类特殊θ-图的Laplacian谱唯一性问题研究

通过θ-图中除了含有一个4圈的θ-图外,其余的θ-图都是邻接谱唯一图的有关结论,研究了几类特殊θ-图的Laplacian谱唯一性问题.即:θ-图θ_(s_1,s_2,s_3)(|s_i-s_j|≤2,1≤i≤3)、圈长为3或4的θ-图以及θ-图θ_0,u,v(u+v=1(mod 2)).     

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

设$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]上提出的一个公开问题.     

ON THE NORMALIZED LAPLACIAN SPECTRUM OF A NEW JOIN OF TWO GRAPHS

Given graphs G_1 and G_2, we define a graph operation on G_1 and G_2,namely the SSG-vertex join of G_1 and G_2, denoted by G_1 G_2. Let S(G) be the subdivision graph of G. The SSG-vertex join G_1G_2 is the graph obtained from S(G_1) and S(G_2) by joining each vertex of G_1 with each vertex of G_2. In this paper, when G_i(i = 1, 2) is a regular graph, we determine the normalized Laplacian spectrum of G_1 G_2. As applications, we construct many pairs of normalized Laplacian cospectral graphs, the normalized Laplacian energy, and the degree Kirchhoff index of G_1G_2.     

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

设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-特征值的不等式序列.     

一类2级一般强正则图

作为强正则图的一种新推广,p级一般强正则图是使得任意两个邻接的顶点和任意两个不邻接的顶点的公共邻接点数都有p种不同取值的非空k-正则图.对于参数为(n,k;a₁,a₂;c₁,c₂)的2级一般强正则图中任一顶点,如果与这个顶点邻接且有a_i (i=1,2)个公共邻接点或者与这个顶点不邻接且有c₁ (i=1,2)个公共邻接点的顶点数与该点的选取无关,则称这个2级一般强正则图为自由的.本文研究了参数为(n,k;k-1,a₂;k-1,c₂)的2级一般强正则图,得到一类自由的2级一般强正则图存在的充要条件.     

围长为g且有k个悬挂点的单圈图的谱半径和Laplacian谱半径

图的谱半径和Laplacian谱半径分别是图的邻接矩阵和Laplacian矩阵的最大特征值.本文中,我们分别刻画了围长为g且有k个悬挂点的单圈图的谱半径和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相似文献   

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

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]给出了两个距离正则图的卡氏积的距离谱.本文计算了联并图和距离正则图的卡氏积及两个联并图的卡氏积的距离谱.在此基础之上,我们得到了两个利用联并图与非同谱距离正则等能量图作卡氏积及联并图作卡氏积构造非同谱等距离能量图族的方法.     

图类■中的整谱图

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

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

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

两类双圈图的Laplacian谱确定问题

设G=(V(G),E(G))是一个简单连通图,V(G),E(G)分别表示图G的顶点集和边集.如果与图G同Laplacian谱的图都与G同构,则称图G由它的Laplacian谱确定.该文定义了两类双圈图Q(n;n_1,n_2,···,nt)和B(n;n_1,n_2),证明了双圈图Q(n;n_1),Q(n;n_1,n_2),Q(n;n_1,n_2,n_3)和双圈图B(n;n_1,n_2)分别由它们的Laplacian谱确定.     

关于图的升分解问题

1987年,文献[1]中给出了图的升分解概念.已知图 G 和自然数 n,G 的边数 q 满足(?)≤q<(?).如果 G 能分解为子图 G_1,G_2,…,G_n 的并,满足 G_i 与G_(i+1)的一个真子图同构(1≤i≤n-1),G_i 不含孤立点,则称这个分解为图 G 的一个升分解.     

包含圈的一些Ramsey数

用两种颜色,比如红和蓝,给完全图K_n的边着色.把着红色和蓝色的边集分别记为E_1和E_2,把K_n的边集分别是E_1和E_2的生成子图分别记为R和B,那么称R和B是K_n的一个分解,记为K_n=R⊕B.图G_1和G_2的Ramsey数,记为r(G_1,G_2),是使得K_n的任意一个分解K_n=R⊕B有R(?)G_1或B(?)G_2的最小正整数n.这里符号G(?)H表示图G包含子图H.此外,用C_n表示长为n的圈,GVH表示图G和H的联图.K_n表示n个相互独立的点,B_n指联图K_2     

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

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

一个最小可行图的判定条件

设有n个集合X_1,…,X_n,一个以X=U_(i=1)~nX_i为顶点集的图G称为是一个关于(X_1,…,X_n)的可行图,如果对每一个X_i(i=1,…,n),导出子图G_i=G[Xi]是连通的。关于集合序列(X_1,…,X_n),含最少边数的可行图称为是最小可行图。本文证明,关于(X_1,X_2,X_3)的可行图G=G_1∪G_2∪G_3是最小可行图的充分必要条件是:当X_i∩X_j∩X_k≠φ(i,j,k)=1,2,3)时,G_i∩G_j∩G_k是树。它发展了由D.-Z.Du(堵丁柱)在1986年得到的一个结果。