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.     

含偶圈图的Laplacian 谱刻画

设 H(K_{1,5},P_n,C_l)是由路 P_n的两个悬挂点分别粘上星图K_{1,5}的悬挂点和圈 C_l的点所得的单圈图. 若两个二部图是关于Laplacian 矩阵同谱的, 则它们的线图是邻接同谱的, 两个邻接同谱图含有相同数目的同长闭回路. 如果任何一个与图G关于Laplacian 同谱图都与图G 同构, 那么称图G可由其Laplacian 谱确定. 利用图与线图之间的关系证明了H(K_{1,5},P_n,C_4)、H(K_{1,5},P_n,C_6) 由它们的Laplacian谱确定.     

On a signless Laplacian spectral characterization of -shape trees

Let M be an associated matrix of a graph G (the adjacency, Laplacian and signless Laplacian matrix). Two graphs are said to be cospectral with respect to M if they have the same M spectrum. A graph is said to be determined by M spectrum if there is no other non-isomorphic graph with the same spectrum with respect to M. It is shown that T-shape trees are determined by their Laplacian spectra. Moreover among them those are determined by their adjacency spectra are characterized. In this paper, we identify graphs which are cospectral to a given T-shape tree with respect to the signless Laplacian matrix. Subsequently, T-shape trees which are determined by their signless Laplacian spectra are identified.     

Towards a spectral theory of graphs based on the signless Laplacian, II

A spectral graph theory is a theory in which graphs are studied by means of eigenvalues of a matrix M which is in a prescribed way defined for any graph. This theory is called M-theory. We outline a spectral theory of graphs based on the signless Laplacians Q and compare it with other spectral theories, in particular to those based on the adjacency matrix A and the Laplacian L. As demonstrated in the first part, the Q-theory can be constructed in part using various connections to other theories: equivalency with A-theory and L-theory for regular graphs, common features with L-theory for bipartite graphs, general analogies with A-theory and analogies with A-theory via line graphs and subdivision graphs. In this part, we introduce notions of enriched and restricted spectral theories and present results on integral graphs, enumeration of spanning trees, characterizations by eigenvalues, cospectral graphs and graph angles.     

On the spectral characterization of the union of complete multipartite graph and some isolated vertices

A graph is said to be determined by its adjacency spectrum (DS for short) if there is no other non-isomorphic graph with the same spectrum. In this paper, we focus our attention on the spectral characterization of the union of complete multipartite graph and some isolated vertices, and all its cospectral graphs are obtained. By the results, some complete multipartite graphs determined by their adjacency spectrum are also given. This extends several previous results of spectral characterization related to the complete multipartite graphs.     

On the p-Ranks of the Adjacency Matrices of Distance-Regular Graphs

Let be a distance-regular graph with adjacency matrix A. Let I be the identity matrix and J the all-1 matrix. Let p be a prime. We study the p-rank of the matrices A + bJ – cI for integral b, c and the p-rank of corresponding matrices of graphs cospectral with .Using the minimal polynomial of A and the theory of Smith normal forms we first determine which p-ranks of A follow directly from the spectrum and which, in general, do not. For the p-ranks that are not determined by the spectrum (the so-called relevant p-ranks) of A the actual structure of the graph can play a rôle, which means that these p-ranks can be used to distinguish between cospectral graphs.We study the relevant p-ranks for some classes of distance-regular graphs and try to characterize distance-regular graphs by their spectrum and some relevant p-rank.     

Spectral Theory for Discrete Laplacians

We give the spectral representation for a class of selfadjoint discrete graph Laplacians Δ, with Δ depending on a chosen graph G and a conductance function c defined on the edges of G. We show that the spectral representations for Δ fall in two model classes, (1) tree-graphs with N-adic branching laws, and (2) lattice graphs. We show that the spectral theory of the first class may be computed with the use of rank-one perturbations of the real part of the unilateral shift, while the second is analogously built up with the use of the bilateral shift. We further analyze the effect on spectra of the conductance function c: How the spectral representation of Δ depends on c.     

The spectral characterization of graphs of index less than 2 with no path as a component

A graph is said to be determined by the adjacency and Laplacian spectrum (or to be a DS graph, for short) if there is no other non-isomorphic graph with the same adjacency and Laplacian spectrum, respectively. It is known that connected graphs of index less than 2 are determined by their adjacency spectrum. In this paper, we focus on the problem of characterization of DS graphs of index less than 2. First, we give various infinite families of cospectral graphs with respect to the adjacency matrix. Subsequently, the results will be used to characterize all DS graphs (with respect to the adjacency matrix) of index less than 2 with no path as a component. Moreover, we show that most of these graphs are DS with respect to the Laplacian matrix.     

Induced Graph Packing Problems

Let H{\mathcal{H}} be a set of undirected graphs. The induced H{\mathcal{H}} -packing problem in an input graph G is to find a subgraph Q of G of maximum size such that each connected component of Q is an induced subgraph of G and is isomorphic to some member of H{\mathcal{H}} . In this paper we focus on the case when H{\mathcal{H}} consists of factor-critical graphs and a certain family of ‘propellers’. Clarifying the methods developed in the related theory of non-induced graph packings, we show a Gallai–Edmonds type structure theorem and a Berge–Tutte type minimax formula. We also give an Edmonds type alternating forest algorithm for the case when H{\mathcal{H}} consists of a sequential set of stars and factor-critical graphs. This simplifies the related result of Egawa, Kano and Kelmans.     

Two characterizations of chain partitioned probe graphs

Chain graphs are exactly bipartite graphs without induced 2K ₂ (a graph with four vertices and two disjoint edges). A graph G=(V,E) with a given independent set S⊆V (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if G can be extended to a chain graph by adding edges between certain vertices in S. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned probe graphs by six forbidden subgraphs. The second one characterizes these graphs via a certain “enhanced graph”: G is a chain partitioned probe graph if and only if the enhanced graph G ^* is a chain graph. This is analogous to a result on interval (respectively, chordal, threshold, trivially perfect) partitioned probe graphs, and gives an O(m ²)-time recognition algorithm for chain partitioned probe graphs.