关于图中存在不含给定k-因子的[a,b]-因子的度条件

设$1\leq a<b, 0\leq k$是整数. 设$G$是一个含有$k$-因子$Q$且阶为$|G|$的图. 设\delta(G)$表示$G$的最小度, 且$\delta(G)\geq a+k$. 如果$Q$连通, 设$\varepsilon=k$, 否则设$\varepsilon=k+1$.证明:当$b\geq a+\varepsilon-1$时, 如果对$G$的任意两个不相邻的点$x$和$y$都有max$\{d_G(x),d_G(y)\}\geq {\rm max}\{{{a|G|} \over {a+b}},{{(|G|+(a-1)(2a+b+\varepsilon-2))} \over {b+1}}\}+k$, 那么$G$有一个$[a, b]$-因子$F$ 使得 $E(F)\cap E(Q)=\emptyset$. 这个度条件是最佳的, 条件$b\geqa+\varepsilon-1$不能去掉. 进一步,得到图存在含给定$k$-因子的$[a, b]$-因子的度条件.     

图的上可嵌入性与围长及相邻顶点度和

$G$是一个阶为$n$围长为$g$的简单图, $u$和$v$是$G$中任意两个相邻顶点, 如果$d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g + 5$, 则$G$是上可嵌入的; 如果$G$是2-\!边连通(或3-\!边连通)图, 则当 $d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g + 3$ (或 $d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g - 5$)时$G$是上可嵌入的, 并且上面3个下界都是紧的.     

半无爪可迹图的度和条件

可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in 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_{v\in 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$-广义拟树的第一个leap Zagreb 指标

图$G$的第一个leap Zagreb指标定义如下: $LM_1(G)=\sum_(v\in v(G)}d_2(v/G)^2$, 其中$d_2(v/G)$是离点$v$的距离为2的顶点. 令$\mathcal{QT}^{(k)}(n)$是有$n$个顶点的$k$-广义拟树的集合.若$G\in \mathcal{QT}^{(k)}(n)$, 本文给出了图$G$的第一个leap Zagreb指标的范围.     

关于数论函数$\sigma(n)$的一个注记

对于两个不相同的正整数$m$和$n$, 如果满足$\sigma(m)=\sigma(n)=m+n$, 则称之为一对亲和数, 这里$\sigma(n)=\sum_{d|n}d$.本文给出了$f(x,y)=x^{2^{x}}+y^{2^{x}}(x>y\geq{1},(x,y)=1)$不与任何正整数构成亲和数对的结论, 这里$x$,$y$具有不同的奇偶性, 即, 关于$z$的方程$\sigma(f(x,y))=\sigma(z)=f(x,y)+z$不存在正整数解.     

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

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

以完全二部图作为星补的正则图的刻画

设$G$是一个$n$阶图, $\mu$是$G$的一个$(k\ge 1)$重邻接特征值. 图$G$中关于$\mu$的星补$H$是指$G$的不含特征值$\mu$的$n-k$阶诱导子图,且顶点集$X=V(G-H)$称为图$G$中关于$\mu$的星集.星补技术提供了利用部分子结构来重建满足特定性质的整个图的谱工具. 本文我们研究了关于特征值$\mu$的以$K_{t,s}~(s\ge t\ge 2)$作为是补的正则图, 特别地, 我们完全刻画了$t=3$的情形, 获得了当$t=s$时的一些性质, 并提出了有待进一步研究的问题.     

图的$A_\alpha$谱半径的注释

设$G$为具有$n$个顶点的简单图, $\rho_\alpha(G)$为其$A_\alpha(G)$谱半径.对图$G$的任一顶点$v_i$, 本文给出了$\rho_\alpha(G)$与$\rho_alpha(G-v_i)$之间的关系.     

图的p-Sombor(拉普拉斯)矩阵的谱性质

最近在化学图论引入的Sombor指数可以预测分子的物理化学性质. 本文从代数的角度来研究($p$-)Sombor指数的性质. $p$-Sombor矩阵$\mathcal{S}_{p}(G)$是一个$n$阶方阵, 当$v_{i}\sim v_{j}$时, 其$(i,j)$位置的元素为$((d_{i})^{p}+(d_{j})^{p})^{\frac{1}{p}}$, 否则为$0$, 其中$d_{i}$表示图$G$中顶点$v_{i}$的度. 该矩阵推广了著名的Zagreb矩阵$(p=1)$、Sombor矩阵$(p=2)$和inverse sum indeg矩阵$(p=-1)$. 本文找到了一对$p$-Sombor非同谱的等能量图, 并确定了$p$-Sombor(拉普拉斯)谱半径的一些界. 然后刻画了具有$k$个不同$p$-Sombor拉普拉斯特征值的连通图的性质. 最后确定了一些特殊图的Sombor谱. 作为推论, 确定了Sombor矩阵$(p=2)$, Zagreb矩阵$(p=1)$和inverse sum indeg矩阵$(p=-1)$的谱性质.     

偶图$K_{n,n+7}-A(|A|\leq3)$的圈长分布唯一性

阶为$n$的图$G$的圈长分布是序列($c_1,c_2,\ldots,c_n$), 其中$c_i$是图$G$中长为$i$的圈数.本文得到如下结果: 设$A\subseteq E(K_{n,n+7})$,在以下情况, 图 $G$ 由其圈长分布唯一确定.(1) $G=K_{n,n+7}$(n\geq10)$;(2) $G=K_{n,n+7}-A$ $(|A|=1,n\geq12)$;(3)$G=K_{n,n+7}-A$(|A|=2,n\geq14)$;(4)$G=K_{n,n+7}-A$ $(|A|=3     

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

循环图的距离能量（英文）

For a connected graph G, the distance energy of G is a recently developed energytype invariant, defined as the sum of absolute values of the eigenvalues of the distance matrix G. A graph is called circulant if it is Cayley graph on the circulant group, i.e., its adjacency matrix is circulant. In this note, we establish lower bounds for the distance energy of circulant graphs. In particular, we discuss upper bound of distance energy for the 4-circulant graph.     

可迹图的谱充分条件

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

On graphs with exactly one anti-adjacency eigenvalue and beyond

The anti-adjacency matrix of a graph is constructed from the distance matrix of a graph by keeping each row and each column only the largest distances. This matrix can be interpreted as the opposite of the adjacency matrix, which is instead constructed from the distance matrix of a graph by keeping in each row and each column only the distances equal to 1. The (anti-)adjacency eigenvalues of a graph are those of its (anti-)adjacency matrix. Employing a novel technique introduced by Haemers (2019) [9], we characterize all connected graphs with exactly one positive anti-adjacency eigenvalue, which is an analog of Smith's classical result that a connected graph has exactly one positive adjacency eigenvalue iff it is a complete multipartite graph. On this basis, we identify the connected graphs with all but at most two anti-adjacency eigenvalues equal to ?2 and 0. Moreover, for the anti-adjacency matrix we determine the HL-index of graphs with exactly one positive anti-adjacency eigenvalue, where the HL-index measures how large in absolute value may be the median eigenvalues of a graph. We finally propose some problems for further study.     

两类六角系统的$A\alpha$-特征多项式和$A\alpha$-谱

2017年, Nikiforov首次提出研究图$G$的$A\alpha$-矩阵, 其定义为:$A\alpha(G)=\alpha D(G)+(1-\alpha)A(G) (\alpha\in [0,1])$, 其中$A(G)$和$D(G)$分别为图$G$的邻接矩阵和度对角矩阵. 设$F_n$和$M_n$分别为圈状六角系统和M\"{o}bius带状六角系统图. 根据循环矩阵的行列式和特征值, 本文首先给出图$F_n$和$M_n$的$A\alph$-特征多项式和$A\alpha$-谱, 进一步得到图$F_n$和$M_n$的$A\alpha$-能量的上界.     

连通图的谱半径上界

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

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

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

Doubly stochastic graph matrices, II

If G is a graph on n vertices, its Laplacian matrix L(G) = D(G) - A(G) is the difference of the diagonal matrix of vertex degrees and the adjacency matrix. The main purpose of this note is to continue the study of the positive definite, doubly stochastic graph matrix (I_n + L(G))-¹= ω(G) = (w_ij). If, for example, w(G) = min w_ij, then w(G)≥0 with equality if and only if G is disconnected and w(G) ≤ l/(n + 1) with equality if and only if G = K_n. If i¦j, then w_ii ≥2wij, with equality if and only if the ith vertex has degree n - 1. In a sense made precise in the note, max w,, identifies most remote vertices of G. Relations between these new graph invariants and the algebraic connectivity emerge naturally from the fact that the second largest eigenvalue of ω(G) is 1/(1 + a(G)).     

Doubly stochastic graph matrices,II

If G is a graph on n vertices, its Laplacian matrix L(G) = D(G) - A(G) is the difference of the diagonal matrix of vertex degrees and the adjacency matrix. The main purpose of this note is to continue the study of the positive definite, doubly stochastic graph matrix (I_n + L(G))?¹= ω(G) = (w_ij). If, for example, w(G) = min w_ij, then w(G)≥0 with equality if and only if G is disconnected and w(G) ≤ l/(n + 1) with equality if and only if G = K_n. If i¦j, then w_ii ≥2wij, with equality if and only if the ith vertex has degree n - 1. In a sense made precise in the note, max w,, identifies most remote vertices of G. Relations between these new graph invariants and the algebraic connectivity emerge naturally from the fact that the second largest eigenvalue of ω(G) is 1/(1 + a(G)).     

完全多部图的无符号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.