关于图的拟拉普拉斯谱半径

用代数方法给出了一个关于简单图的顶点度数与拟拉普拉斯谱半径的不等式,并给出了图的拟拉普拉斯谱半径的一个新上界.     

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

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

恰有k个悬挂点的n阶双圈和三圈图的拟拉普拉斯谱半径

设k,n为两个确定的正整数.本文得到了当1≤k≤n-7时恰有k个悬挂点的n阶连通三圈图的最大拟拉普拉斯谱半径的唯一极图,也得到了当1≤k≤n-5时恰有k个悬挂点的n阶连通双圈图的最大拟拉普拉斯谱半径的唯一极图.     

具有固定围长的单圈图的无号拉普拉斯谱半径

研究了单圈图的无号拉普拉斯谱半径,给出了具有固定围长的单圈图的无号拉普拉斯谱半径最大的图.     

无符号拉普拉斯谱半径的新上界

如果一个图存在定向满足其最大出度△~＋不超过最大度△的一半,则通过估计图的半边路径（semi-edge walk）的个数,得到了该图的无符号拉普拉斯谱半径的一个新上界.进而根据D.Goncalves对平面图边分解的结果,得到了平面图无符号拉普拉斯谱半径的一个新上界.     

可迹图的谱充分条件

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

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

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

关于{P2, Ci| i≥3}-覆盖图

设 Ｇ是一个图,若对于 Ｇ的任意一边 Ｇ都有｛Ｐ_２,Ｃｉ｜ｉ－＞３｝－因子含有这条边,则称Ｇ是｛Ｐ_２,Ｃｉ｜ｉ－＞３｝－覆盖图．本文给出连通非二分图Ｇ是｛Ｐ２,Ｃｉ｜ｉ－＞３｝－覆盖图的充要条件为任给Ｓ■Ｖ（Ｇ）,Ｖ（Ｇ）≠Ｓ≠■有ｉ（Ｇ－Ｓ）＿＞｜Ｓ｜－１成立．     

一些图的拟拉普拉斯能量和基尔霍夫指标（英文）

G是具有拉普拉斯特征值μ1≥μ2≥···≥μn=0的的n阶连通图.G的拟拉普拉斯能量和基尔霍夫指标分别定义为LEL=∑n-1i=1√μi和Kf=n∑n-1i=11/μi.本文研究半正则图的线图及正则图细分图的线图,给出这两类图的拟拉普拉斯能量和基尔霍夫指标的界,同时获得它们的基尔霍夫指标公式.     

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

混合图的Hermitian邻接矩阵的零维数

A mixed graph means a graph containing both oriented edges and undirected edges. The nullity of the Hermitian-adjacency matrix of a mixed graph G, denoted by ηH(G),is referred to as the multiplicity of the eigenvalue zero. In this paper, for a mixed unicyclic graph G with given order and matching number, we give a formula on ηH(G), which combines the cases of undirected and oriented unicyclic graphs and also corrects an error in Theorem 4.2 of [Xueliang LI, Guihai YU. The skew-rank of oriented graphs. Sci. Sin. Math., 2015, 45:93-104(in Chinese)]. In addition, we characterize all the n-vertex mixed graphs with nullity n-3, which are determined by the spectrum of their Hermitian-adjacency matrices.     

图的邻接矩阵的行列式与积和式的递推表达式

设A(G)是简单图G的邻接矩阵,H是由G的独立边和不交圈组成的生成子图的集合,e是H中某个图的独立边,C是H中图的圈,且e∈E(C).记G-e是G的删边子图,G\W是从G中删去导出子图W中的顶点及其关联边后得到的图.那么A(G)的行列式为detA(G)=detA(G-e)-detA(G\e)-2(-1)~(|V(C)|)detA(G\C)A(G)的积和式为perA(G)=perA(G-e)+perA(G\e)+2perA(G\C)这里,C取遍H中图的经过边e的圈.     

关于有限群的强幂图的谱

令$G$是一个阶为$n$的有限群, $G$上的强幂图定义为: 以$G$为顶点集, 对于两个不同的元素$x$和$y$, 如果存在两个不超过$n$的正整数$n_1, n_2$使得$x^{n_1}=y^{n_2}$, 则$x$和$y$ 之间连一条边. 本文给出了$G$上强幂图的距离矩阵和邻接矩阵的特征多项式, 并且计算了其距离谱和邻接谱.     

一类可逆矩阵逆矩阵的图论解法

设 M( G)是简单无向图 G的关联矩阵 ,A是 M( G)的可逆子矩阵 ,γ( A)是逆矩阵 A- 1中非零元素的个数 .获得了求逆矩阵 A- 1的一种图论方法 ,并且得到了γ( A)的精确上下界以及达到上下界时子矩阵 A的图论刻划     

有关循环图C(n;{1,k})的独立数的一些结果

令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记作α(G).本文研究了循环图C(n;{1,k})的独立数问题,并给出了当k=2,3,4,5时的准确值.     

Normal subgroup based power graph of finite groups

Ricerche di Matematica - Let G be a finite group and $$N \unlhd G$$ . The normal subgroup based power graph of G, $$\Gamma _N(G)$$ , is an undirected graph with vertex set $$(G{\setminus }N) \cup...     

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

设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阶单圈图和双圈图的最大的无符号拉普拉斯分离度,并分别刻画了相应的极图.     

Optimum matching forests II: General weights

Matching forests generalize branchings in a directed graph and matchings in an undirected graph. We present an efficient algorithm, the PMF Algorithm, for the problem: given a mixed graphG and a real weight on each of its edges, find a perfect matching forest of maximum weight-sum. The PMF Algorithm proves the sufficiency of a linear system which definesP ⁼ (G) andP(G), the convex hull of incidence vectors of perfect matching forests and matching forests respectively ofG. The algorithm also provides a generalization of Tutte's theorem on the existence of perfect matchings in an undirected graph.Research partially supported by a N.R.C. of Canada Postdoctorate Fellowship.