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

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

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

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

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

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

二部图的单特征值

一个图的特征值通常指的是它的邻接矩阵的特征值,在图的所有特征值中,重数为1的特征值即所谓的单特征值具有特殊的重要性.确定一个图的单特征值是一个比较困难的问题,主要是没有一个通用的方法.1969年,Petersdorf和Sachs给出了点传递图单特征值的取值范围,但是对于具体的点传递图还需要根据图本身的特性来确定它的单特征值.给出一类正则二部图,它们是二面体群的凯莱图,这类图的单特征值中除了它的正、负度数之外还有0或者±1,而它们恰好是Petersdorf和Sachs所给出的单特征值范围内的中间取值.     

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

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

图的正(负)特征值平方和界的估计

图G的特征值是指该图邻接矩阵的特征值,图G的正特征值平方和用符号S+(G)表示.关于图的正(负)特征值平方和界的估计,[Discrete Math.,2016,339(9):2215-2223]给出一个有趣的猜想:对于连通图G有min{S-(G),S+(G)}≥n-1,其中n表示图G的顶点数,S-(G)表示图G负特征值...     

匹配数为2的图的最小特征值

在所有给定阶数且匹配数为2的连通图中,我们刻画了最小特征值达到极小的图,给出了这类图最小特征值的下界.     

恰有两个主特征值的图的性质

设λ是图G的一个特征值,如果存在属于λ的一个特征向量X=(x_1,x_2,…,x_n)~T,使得(?)x_i≠0,则λ称为图G的主特征值.将恰有两个主特征值的一个充要条件做了进一步推广,并在此基础上给出恰有两个主特征值的图的一些性质以及恰有两个主特征值的图的一些运算结果.     

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

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

四圈图的Spread

图的spread定义为图的邻接矩阵的最大特征值与最小特征值的差.本文确定了n(n≥84)顶点四圈图中spread最大的唯一的图.     

Algebraic conditions for <Emphasis Type="Italic">t</Emphasis>-tough graphs

We give some algebraic conditions for t-tough graphs in terms of the Laplacian eigenvalues and adjacency eigenvalues of graphs.     

Graphs with three distinct eigenvalues and largest eigenvalue less than 8

In this paper we consider graphs with three distinct eigenvalues and, we characterize those with the largest eigenvalue less than 8. We also prove a simple result which gives an upper bound on the number of vertices of graphs with a given number of distinct eigenvalues in terms of the largest eigenvalue.     

Trees with very few eigenvalues

The number of distinct eigenvalues of the adjacency matrix of a graph is bounded below by the diameter of the graph plus one. Many graphs that achieve this lower bound exhibit much symmetry, for example, distance-transitive and distance-regular graphs. Here we provide a recursive construction that will create graphs having the fewest possible eigenvalues. This construction is best at creating trees, but will also create cyclic graphs meeting the lower bound. Unlike the graphs mentioned above, many of the graphs constructed do not exhibit large amounts of symmetry. A corollary allows us to determine the values and multiplicities of all the nonsimple eigenvalues of the constructed graph.     

Limit points of eigenvalues of (di)graphs

The study on limit points of eigenvalues of undirected graphs was initiated by A. J. Hoffman in 1972. Now we extend the study to digraphs. We prove 1. Every real number is a limit point of eigenvalues of graphs. Every complex number is a limit point of eigenvalues of digraphs. 2. For a digraph D, the set of limit points of eigenvalues of iterated subdivision digraphs of D is the unit circle in the complex plane if and only if D has a directed cycle. 3. Every limit point of eigenvalues of a set D of digraphs (graphs) is a limit point of eigenvalues of a set of bipartite digraphs (graphs), where consists of the double covers of the members in D. 4. Every limit point of eigenvalues of a set D of digraphs is a limit point of eigenvalues of line digraphs of the digraphs in D. 5. If M is a limit point of the largest eigenvalues of graphs, then −M is a limit point of the smallest eigenvalues of graphs.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

Eigenvalues of graphs with vertices of large degree at distance three apart

We investigate the family of graphs with many large eigenvalues. It is not hard to see that every graph with many vertices of large degree that are pairwise at distance at least four from each other, has many large eigenvalues. We show that this does not hold if the vertices of large degree are at mutual distance three from each other. We explore this class of graphs further and provide some bounds on their eigenvalues.     

Schrödinger operators on periodic discrete graphs

We consider Schrödinger operators with periodic potentials on periodic discrete graphs. The spectrum of the Schrödinger operator consists of an absolutely continuous part (a union of a finite number of non-degenerated bands) plus a finite number of flat bands, i.e., eigenvalues of infinite multiplicity. We obtain estimates of the Lebesgue measure of the spectrum in terms of geometric parameters of the graph and show that they become identities for some class of graphs. Moreover, we obtain stability estimates and show the existence and positions of large number of flat bands for specific graphs. The proof is based on the Floquet theory and the precise representation of fiber Schrödinger operators, constructed in the paper.