Q整图新类

对于一个简单图G, 方阵Q(G)=D(G)+A(G)称为G的无符号拉普拉斯矩阵,其中D(G)和A(G)分别为G的度对角矩阵和邻接矩阵. 一个图是Q整图是指该图的无符号拉普拉斯矩阵的特征值全部为整数.首先通过Stanic 得到的六个顶点数目较小的Q整图,构造出了六类具有无穷多个的非正则的Q整图. 进而,通过图的笛卡尔积运算得到了很多的Q整图类. 最后, 得到了一些正则的Q整图.     

单圈图和双圈图的最大无符号拉普拉斯分离度

设G是一个n阶简单图,q_{1}(G)\geq q_{2}(G)\geq \cdots \geq q_{n}(G)是其无符号拉普拉斯特征值. 图G的无符号拉普拉斯分离度定义为S_{Q}(G)=q_{1}(G)-q_{2}(G). 确定了n阶单圈图和双圈图的最大的无符号拉普拉斯分离度,并分别刻画了相应的极图.     

关于图的最小Q-特征值

研究了基于n阶二部图和s阶完全图构造的一个图类,得到了该图类的无符号拉普拉斯最小特征值(即最小Q-特征值)的一个可达上界为s.基于此,对于任意给定的正整数s和正偶数n,构造了最小Q-特征值为s的一类n+s阶图.另外,对于任意给定的最小度δ和阶数n,在满足2≤δ≤n-1/2条件下,构造了最小Q-特征值为δ-1的一类n阶图.     

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

假设图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的三圈图中无符号拉普拉斯谱半径最大的图的结构.     

哈密顿图的无符号拉普拉斯谱半径条件

令A(G)=(a_(ij))_(n×n)是简单图G的邻接矩阵,其中若v_i-v_j,则a_(ij)=1,否则a_(ij)=0.设D(G)是度对角矩阵,其(i,i)位置是图G的顶点v_i的度.矩阵Q(G)=D(G)+A(G)表示无符号拉普拉斯矩阵.Q(G)的最大特征根称作图G的无符号拉普拉斯谱半径,用q(G)表示.Liu,Shiu and Xue[R.Liu,W.Shui,J.Xue,Sufficient spectral conditions on Hamiltonian and traceable graphs,Linear Algebra Appl.467(2015)254-255]指出:可以通过复杂的结构分析和排除更多的例外图,当q(G)≥2n-6+4/(n-1)时,则G是哈密顿的.作为论断的有力补充,给出了图是哈密顿图的一个稍弱的充分谱条件,并给出了详细的证明和例外图.     

五类特殊图的三种距离矩阵的特征多项式

设G是一个具有顶点集V(G)={v_1,v_2,…,u_n}的n阶简单图.设d_(i,j)=d(v_i,v_j)表示图G中任意两个顶点v_i与v_j的距离.矩阵D(G)=[d_(i,j)]_(n×n)定义为图G的距离矩阵.定义Tr(v)=∑_(ueV(G))d(u,u)为图G中顶点u的点传递度.Diag(Tr)表示以G中顶点的点传递度为主对角线上元素的对角矩阵.则矩阵D~L(G)=Diag(Tr)一D(G)和D~Q(G)=Diag(Tr)+D(G)分别定义为图G的距离拉普拉斯矩阵和距离无符号拉普拉斯矩阵.分别得到五类特殊图的距离,距离拉普拉斯,距离无符号拉普拉斯的特征多项式的一般表达式.     

可迹图的谱充分条件

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

给定顶点数和边数的连通图的Q-谱半径的界

图的无符号拉普拉斯矩阵是图的邻接矩阵和度对角矩阵的和,其特征值记为q1≥q2≥…≥qn.设C(n,m)是由n个顶点m条边的连通图构成的集合,这里1≤n-1≤m≤(n2).如果对于任意的G∈C(n,m)都有q1(G*)≥q1(G)成立,图G*∈C(n,m)叫做最大图.这篇文章证明了对任意给定的正整数a=m-n+1,如果n...     

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

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

图的无符号拉普拉斯和距离无符号拉普拉斯特征值

Let G be a simple graph. We first show that ■, where δiand di denote the i-th signless Laplacian eigenvalue and the i-th degree of vertex in G, respectively.Suppose G is a simple and connected graph, then some inequalities on the distance signless Laplacian eigenvalues are obtained by deleting some vertices and some edges from G. In addition, for the distance signless Laplacian spectral radius ρQ(G), we determine the extremal graphs with the minimum ρQ(G) among the trees with given diameter, the unicyclic and bicyclic graphs with given girth, respectively.     

完全多部图的无符号Laplacian特征多项式(英文)

For a simple graph G,let matrix Q（G）=D（G） + A（G） be it’s signless Laplacian matrix and Q G （λ）=det（λI Q） it’s signless Laplacian characteristic polynomial,where D（G） denotes the diagonal matrix of vertex degrees of G,A（G） denotes its adjacency matrix of G.If all eigenvalues of Q G （λ） are integral,then the graph G is called Q-integral.In this paper,we obtain that the signless Laplacian characteristic polynomials of the complete multi-partite graphs G=K（n₁,n₂,···,n_t）.We prove that the complete t-partite graphs K（n,n,···,n）t are Q-integral and give a necessary and sufficient condition for the complete multipartite graphs K（m,···,m）s（n,···,n）t to be Q-integral.We also obtain that the signless Laplacian characteristic polynomials of the complete multipartite graphs K（m,···,m,）s1（n,···,n,）s2（l,···,l）s3.     

Graphs with at most one signless Laplacian eigenvalue exceeding three

We determine all connected graphs with at most one signless Laplacian eigenvalue exceeding three.     

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

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

给定围长的三圈图的无符号拉普拉斯谱半径

A tricyclic graph G =（V（G）, E（G）） is a connected and simple graph such that｜E（G）｜ = ｜V（G）｜＋2. Let Tg nbe the set of all tricyclic graphs on n vertices with girth g. In this paper, we will show that there exists the unique graph which has the largest signless Laplacian spectral radius among all tricyclic graphs with girth g containing exactly three（resp., four）cycles. And at the same time, we also give an upper bound of the signless Laplacian spectral radius and the extremal graph having the largest signless Laplacian spectral radius in Tg n,where g is even.     

Signless Laplacian spectral characterization of 4-rose graphs

A rose graph with p petals (or p-rose graph) is a graph obtained by taking p cycles with just a vertex in common. In this paper, we prove that all 4-rose graphs are determined by their signless Laplacian spectra.     

Spectra of Corona Based on the Total Graph

For two simple connected graphs $G_1$ and $G_2$, we introduce a new graph operation called the total corona $G_1⊛G_2$ on $G_1$ and $G_2$ involving the total graph of $G_1.$ Subsequently, the adjacency (respectively, Laplacian and signless Laplacian) spectra of $G_1⊛G_2$ are determined in terms of these of a regular graph $G_1$ and an arbitrary graph $G_2.$ As applications, we construct infinitely many pairs of adjacency (respectively, Laplacian and signless Laplacian) cospectral graphs. Besides we also compute the number of spanning trees of $G_1⊛G_2.$