可迹图的谱充分条件

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

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

令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是哈密顿的.作为论断的有力补充,给出了图是哈密顿图的一个稍弱的充分谱条件,并给出了详细的证明和例外图.     

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$的距离无符号拉普拉斯谱半径. 本文确定了给定点数的双圈图中具有最大的距离无符号拉普拉斯谱半径的图.     

Halin图$Q$-谱半径的最大值

The Q-index of a graph G is the largest eigenvalue q(G) of its signless Laplacian matrix Q(G). In this paper, we prove that the wheel graph W_n = K_1 ∨C_(n-1)is the unique graph with maximal Q-index among all Halin graphs of order n. Also we obtain the unique graph with second maximal Q-index among all Halin graphs of order n.     

给定顶点数和边数的连通图的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...     

半无爪可迹图的度和条件

可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)cup{v}$, $J(u,v)={win N(u)cap N(v):N(w)subseteq N[u]cup N[v]}$.若图中任意距离为2的两点$u,v$满足$J(u,v)neq emptyset$,则称该图为半无爪图.令$sigma_{k}(G)=min{sum_{vin S}d(v):S$为$G$中含有$k$个点的独立集},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$sigma_{3}(G)geq {n-2}$,则图$G$为可迹图; 文中给出一个图例,说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$sigma_{2}(G)geq frac{2({n-2})}{3}$,则该图为可迹图.     

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

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

二部图是可迹的一个充分条件

本文证明了以下结果:设G=(X,Y;E)是连通的二部图,如果4≤|Y|≤|X|≤|Y|+1,且NC_2≥|X|-1,则G是可迹的。从而表明[2]中的猜想对二部图是成立的。     

直径为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的具有最小拉普拉斯谱半径的村.     

Distance signless Laplacian spectral radius and Hamiltonian properties of graphs

In this paper, we establish a sufficient condition on distance signless Laplacian spectral radius for a bipartite graph to be Hamiltonian. We also give two sufficient conditions on distance signless Laplacian spectral radius for a graph to be Hamilton-connected and traceable from every vertex, respectively. Furthermore, we obtain a sufficient condition for a graph to be Hamiltonian in terms of the distance signless Laplacian spectral radius of the complement of a graph G.     

Some sufficient spectral conditions on Hamilton-connected and traceable graphs

In this paper, we establish some sufficient conditions for a graph to be Hamilton-connected in terms of the edge number, the spectral radius and the signless Laplacian spectral radius of the graph. Furthermore, we also give some sufficient conditions for a graph to be traceable from every vertex in terms of the edge number, the spectral radius and the signless Laplacian spectral radius.     

Spectral results on Hamiltonian problem

Let $\alpha$ be a non-negative real number, and let $\Theta (G,\alpha )$ be the largest eigenvalue of $A\left(G\right)+\alpha D\left(G\right)$. Specially, $\Theta (G,0)$ and $\Theta (G,1)$ are called the spectral radius and signless Laplacian spectral radius of $G$, respectively. A graph $G$ is said to be Hamiltonian (traceable) if it contains a Hamiltonian cycle (path), and a graph $G$ is called Hamilton-connected if any two vertices are connected by a Hamiltonian path in $G$. The number of edges of $G$ is denoted by $e\left(G\right)$. Recently, the (signless Laplacian) spectral property of Hamiltonian (traceable, Hamilton-connected) graphs received much attention. In this paper, we shall give a general result for all these existed results. To do this, we first generalize the concept of Hamiltonian, traceable, and Hamilton-connected to $s$-suitable, and we secondly present a lower bound for $e\left(G\right)$ to confirm the existence of $s$-suitable graphs. Thirdly, when $0\le \alpha \le 1$, we obtain a lower bound for $\Theta (G,\alpha )$ to confirm the existence of $s$-suitable graphs. Consequently, our results generalize and improve all these existed results in this field, including the main results of Chen et al. (2018), Feng et al. (2017), Füredi et al. (2017), Ge et al. (2016), Li et al. (2016), Nikiforov et al. (2016), Wei et al. (2019) and Yu et al. (2013, 2014).     

变换图的正则性和谱半径

在前人对八种变换图研究的基础上,探讨了变换后满足正则性的原图的性质,得到了如下结果:G~( )及G~(---)是正则图当且仅当G是正则图;G~( -)和G~(-- )为正则图的充要条件是G为C_n、K_(2,n-2)或K_4;G~( - )和G~(- -)是正则图当且仅当G为C_5、K_7、K_2、K_(3,3)或G_0;G~(- )和G~( --)是正则的当且仅当G是(n-1)/2-正则图．同时还讨论了变换图的谱半径上界,并对这些上界进行了估计．     

连通图的谱半径上界

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

The Signless Laplacian Spectral Radius of Tricyclic Graphs with k Pendant Vertices

In this paper,we determine the unique graph with the largest signless Laplacian spectral radius among all the tricyclic graphs with n vertices and k pendant vertices.     

无向图可迹的一个充分条件

无向图G是简单连通图,且最小度为δ.如果G中包含一条生成路,则G是可迹的.无向图G的叶子数L(G)是G中生成树所含的叶子数的最大数.基于L(G)和δ,证明了一个充分条件使得无向图G是可迹的,即设G为连通图,最小度为δ≤4.若δ≥1/2(L(G)+2),G是可迹的.