不含P_t的非二部连通图的最小Q-特征值

对于一个连通图而言,它的最小Q-特征值为零当且仅当它是二部图.图的最小Q-特征值常被用来衡量一个图的非二部程度,因而受到研究者的广泛关注.文中研究了图中存在长路的最小Q-特征值条件,分别确定了最小Q-特征值最小的不含路Pt的非二部单圈图和非二部连通图.     

补图具有悬挂点且连通的图的最小特征值

图的最小特征值定义为图的邻接矩阵的最小特征值,它是刻画图的结构性质的重要参数.在给定阶数且补图为具有悬挂点的连通图的图类中,刻画了最小特征值达极小的唯一图,并给出了这类图最小特征值的下界.     

补图为2-点或2-边连通的图的最小特征值

图的最小特征值定义为图的邻接矩阵的最小特征值,是刻画图结构性质的一个重要代数参数. 在所有给定阶数的补图为2-点或2-边连通的图中, 刻画了最小特征值达到极小的唯一图, 并给出了这类图最小特征值的下界.     

4p阶三度点传递图

一个图称为点传递图或对称图如果它的自同构群分别在点集或点集有序对上传递.设P为素数,给出了4p阶连通三度点传递图分类(徐明曜等在[Chin.Ann.Math.,2004,25B(4):545-554]中分类了4p阶连通三度对称图).确定了4p阶互不同构的连通三度点传递图的个数f(4p);当P=2,3,5,7时,f(4p)分别为2,4,8,6;当P≥11且4|(p-1)时,f(4p)=5+p-3/2,当P≥11且4|(p-1)时,f(4p)=3+p-3/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-特征值的不等式序列.     

准传递定向图上的Seymour点

有向图D是准传递的,如果对D中任意三个不同的顶点x, y和z,只要在D中存在弧xy, yz, x和z之间就至少存在一条弧. Seymour二次邻域猜想为:在任何一个定向图D中都存在一个顶点x,满足d_D~+(x)d_D~(++)(x).这里,定向图是指没有2圈的有向图.称满足Seymour二次邻域猜想的点为Seymour点. Fisher证明了Seymour二次邻域猜想适用于竞赛图,也就是每个竞赛图至少包含一个Seymour点. Havet和Thomassé证明了,无出度为零的点的竞赛图至少包含两个Seymour点.注意到,竞赛图是准传递有向图的子图类.研究Seymour二次邻域猜想在准传递定向图上的正确性,通过研究准传递定向图与扩张竞赛图的Seymour点之间的关系,证明了准传递定向图上Seymour二次邻域猜想的正确性,得到:每个准传递定向图至少包含一个Seymour点;无出度为零的点的准传递定向图至少包含两个Seymour点.     

恰有两个Q-主特征值的三圈图

图G的无符号拉普拉斯矩阵定义为图G的邻接矩阵与度对角矩阵的和,其特征值称为图G的Q-特征值.图G的一个Q-特征值称为Q-主特征值,如果它有一个特征向量其分量的和不等于零.确定了所有恰有两个Q-主特征值的三圈图.     

第二小阶数的双本原半对称图

如果一个正则图是边传递但不是点传递的,那么我们称它是半对称的.每一个半对称图X必定是两部分点数相等的二部图,并且它的自同构群Aut(X)在每一部分上是传递的.如果一个半对称图的自同构群在每一部分上作用是本原的,那么我们称它是双本原的.本文决定了第二小阶数的双本原半对称图.     

有循环极大子群的素数幂阶群的作用是边传递的图(Ⅰ)

Γ是一个有限的、单的、无向的且无孤立点的图, G是Aut(Γ)的一个子群.如果G在Γ的边集合上传递,则称Γ是G-边传递图.我们完全分类了当G为一个有循环的极大子群的素数幂阶群时的G-边传递图.这扩展了Sander的结果.本文仅给出其中的一种情况,即当G同构于群时,所有的G-边传递图.结果为,是G-边传递的当且仅当Γ为下列图之一     

容许二维线性群作用点本原的二弧传递图

一个图称为本原的如果它的自同构群作用在点集上是本原的.在这篇文章里,我们不但完全分类了容许一类二维线性群作用点本原的2-弧传递图,而且决定了他们的自同构群,并在同构意义下决定了它们的个数.     

Graphs equienergetic with edge-deleted subgraphs

The energy of a graph is the sum of the absolute values of the eigenvalues of its adjacency matrix. Two graphs are equienergetic if they have the same energy. We construct infinite families of graphs equienergetic with edge-deleted subgraphs.     

The distance-regular graphs such that all of its second largest local eigenvalues are at most one

In this paper, we classify distance regular graphs such that all of its second largest local eigenvalues are at most one. Also we discuss the consequences for the smallest eigenvalue of a distance-regular graph. These extend a result by the first author, who classified the distance-regular graphs with smallest eigenvalue .     

树和单圈图的斜谱矩

给定图$G$,对图$G$的每条边确定一个方向,称为$G$的定向图$G^\sigma$, $G$称为$G^\sigma$的基础图. $G^\sigma$的斜邻接矩阵$S(G^\sigma)$是反对称矩阵,其特征值是0或纯虚数. $S(G^\sigma)$所有特征值的$k$次幂之和称为$G^\sigma$的$k$阶斜谱矩,其中$k$是非负整数.斜谱矩序列可用于对图进行排序.本文主要研究定向树和定向单圈图的斜谱矩,并对这两类图的斜谱矩序列依照字典序进行排序.首先确定了直径为$d$的树作为基础图的所有定向树中,斜谱矩序最大的$2\lfloor\frac{d}{4}\rfloor$个图; 然后确定以围长为$g$的单圈图作为基础图的所有定向单圈图中, 斜谱矩序最大的$2\lfloor\frac{g}{4}\rfloor+1$个图.     

On the Laplacian integral tricyclic graphs

A graph is called Laplacian integral if all its Laplacian eigenvalues are integers. In this paper, we give an edge subdividing theorem for Laplacian eigenvalues of a graph (Theorem 2.1) and characterize a class of k-cyclic graphs whose algebraic connectivity is less than one. Using these results, we determine all the Laplacian integral tricyclic graphs. Furthermore, we show that all the Laplacian integral tricyclic graphs are determined by their Laplacian spectra.     

On Strongly Regular Graphs with k=2μ and Their Extensions

We obtain a convenient expression for the parameters of a strongly regular graph with k=2 in terms of the nonprincipal eigenvalues x and –y. It turns out in particular that such graphs are pseudogeometric for pG _x(2x,y–1). We prove that a strongly regular graph with parameters (35,16,6,8) is a quotient of the Johnson graph (8,4). We also find the parameters of strongly regular graphs in which the neighborhoods of vertices are pseudogeometric graphs for pG _x(2x,t),x3. In consequence, we establish that a connected graph in which the neighborhoods of vertices are pseudogeometric graphs for pG ₃(6,2) is isomorphic to the Taylor graph on 72 vertices or to the alternating form graph Alt(4,2) with parameters (64,35,18,20).     

Balanced Cayley graphs and balanced planar graphs

A balanced graph is a bipartite graph with no induced circuit of length . These graphs arise in integer linear programming. We focus on graph-algebraic properties of balanced graphs to prove a complete classification of balanced Cayley graphs on abelian groups. Moreover, in this paper, we prove that there is no cubic balanced planar graph. Finally, some remarkable conjectures for balanced regular graphs are also presented. The graphs in this paper are simple.     

The new upper bounds on the spectral radius of weighted graphs

Let us consider weighted graphs, where the weights of the edges are positive definite matrices. The eigenvalues of a weighted graph are the eigenvalues of its adjacency matrix and the spectral radius of a weighted graph is also the spectral radius of its adjacency matrix. In this paper, we obtain two upper bounds for the spectral radius of weighted graphs and compare with a known upper bound. We also characterize graphs for which the upper bounds are attained.     

恰有两个主特征值的图与图的剖分

大量研究表明,图的主特征值的数量与图的结构有着密切关系.通过恰有两个主特征值的图的特征定义了2-邻域k-剖分图,研究了恰有两个主特征值的图与2-邻域k-剖分图之间的关系;同时给出一个2-邻域k-剖分图在k=2,3时为等部剖分的条件.     

Some constructions of integral graphs

A graph is called integral if all eigenvalues of its adjacency matrix consist entirely of integers. Integral graphs are very rare and difficult to find. In this article, we introduce some general methods for constructing such graphs. As a consequence, some infinite families of integral graphs are obtained.     

图的代数连通度的界(英文)

本文首先给出了简单图的度序列的平方和的上界,利用这些结果,求出了简单图的代数连通度的几个上下界并确定了它们的临界图。另外,文章也给出了加权图的代数连通度的一个下界。