Spectral Characterizations of Some Distance-Regular Graphs

When can one see from the spectrum of a graph whether it is distance-regular or not? We give some new results for when this is the case. As a consequence we find (among others) that the following distance-regular graphs are uniquely determined by their spectrum: The collinearity graphs of the generalized octagons of order (2,1), (3,1) and (4,1), the Biggs-Smith graph, the M ₂₂ graph, and the coset graphs of the doubly truncated binary Golay code and the extended ternary Golay code.     

关于两个图的一类新连接图的谱

给定2个图G1和G2，设G1的边集E(G1)={e1,e2,?,em1}，则图G1⊙G2可由一个G1，m1个G2通过在G1对应的每条边外加一个孤立点，新增加的点记为U={u1,u2,?,um1}，将ui分别与第i个G2的所有点以及G1中的边ei的端点相连得到，其中i=?1,2,?,m1。得到：（i）当G1是正则图，G2是正则图或完全二部图时，确定了G1⊙G2的邻接谱（A-谱）。（ii）当G1是正则图，G2是任意图时，给出了G1⊙G2的拉普拉斯谱（L-谱）。（iii）当G1和G2都是正则图时，给出了G1⊙G2的无符号拉普拉斯谱（Q-谱）。作为以上结论的应用，构建了无限多对A-同谱图、L-同谱图和Q-同谱图；同时当G1是正则图时，确定了G1⊙G2支撑树的数量和Kirchhoff指数。     

Laplacian spectral characterization of disjoint union of paths and cycles

The Laplacian spectrum of a graph consists of the eigenvalues (together with multiplicities) of the Laplacian matrix. In this article we determine, among the graphs consisting of disjoint unions of paths and cycles, those ones which are determined by the Laplacian spectrum. For the graphs, which are not determined by the Laplacian spectrum, we give the corresponding cospectral non-isomorphic graphs.     

完全图删边子图的子刻画

In this paper, we show that some edges-deleted subgraphs of complete graph are determined by their spectrum with respect to the adjacency matrix as well as the Laplacian matrix.     

Spectral characterization of line graphs of starlike trees

Two graphs are said to be A-cospectral if they have the same adjacency spectrum. A graph G is said to be determined by its adjacency spectrum if there is no other non-isomorphic graph A-cospectral with G. A tree is called starlike if it has exactly one vertex of degree greater than 2. In this article, we prove that the line graphs of starlike trees with maximum degree at least 12 are determined by their adjacency spectra.     

基于拉普拉斯谱确定的两类树

设图G是简单连通图.如果任何一个与图G关于拉普拉斯矩阵同谱的图,都与图G同构,称图G可由其拉普拉斯谱确定.定义了树Y_n和树F(2,n,1)两类特殊结构的树.利用同谱图线图的特点,证明了树Y_n和树F(2,n,1)可由其拉普拉斯谱确定.     

Large Families of Cospectral Graphs

Seidel switching is an operation on graphs G satisfyingcertain regularity properties so that the resulting graph Hhas the same spectrum as G. If G issimple then the complement of G and the complementof H are also cospectral. We use a generalizationof Seidel switching to construct exponentially large familiesof cospectral graphs with cospectral complements.