Search

We present the first steps towards the determination of the signed graphs for which the adjacency matrix has all but at most two eigenvalues equal to ±1. Here we deal with the disconnected, the bipartite and the complete signed graphs. In addition, we present many examples which cannot be obtained from an unsigned graph or its negative by switching. [ABSTRACT FROM AUTHOR]

We complete the determination of the signed graphs for which the adjacency matrix has all but at most two eigenvalues equal to ±1. The unsigned graphs and the disconnected, the bipartite and the complete signed graphs with this property have already been determined in two earlier papers. Here we deal with the remaining cases. [ABSTRACT FROM AUTHOR]

Hoffman's ratio bound is an upper bound for the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix. The bound has proved to be very useful and has been applied many times. Hoffman did not publish his result, and for a great number of users the emergence of Hoffman's bound is a black hole. With his note I hope to clarify the history of this bound and some of its generalizations. [ABSTRACT FROM AUTHOR]

A universal adjacency matrix of a graph G with adjacency matrix A is any matrix of the form U = α A + β I + γ J + δ D with α ≠ 0 , where I is the identity matrix, J is the all-ones matrix and D is the diagonal matrix with the vertex degrees. In the case that G is the disjoint union of regular graphs, we present an expression for the characteristic polynomials of the various universal adjacency matrices in terms of the characteristic polynomials of the adjacency matrices of the components. As a consequence we obtain a formula for the characteristic polynomial of the Seidel matrix of G , and the signless Laplacian of the complement of G (i.e. the join of regular graphs). The main tool is a simple but useful lemma on equitable matrix partitions. With this note we also want to propagate this technique. [ABSTRACT FROM AUTHOR]

Properties of graphs that can be characterized by the spectrum of the adjacency matrix of the graph have been studied systematically recently. Motivated by the complexity of these properties, we show that there are such properties for which testing whether a graph has that property can be NP-hard (or belong to other computational complexity classes consisting of even harder problems). In addition, we discuss a possible spectral characterization of some well-known NP-hard properties. In particular, for every integer k ≥ 6 we construct a pair of k -regular cospectral graphs, where one graph is Hamiltonian and the other one not. [ABSTRACT FROM AUTHOR]

For vertex- and edge-connectivity we construct infinitely many pairs of regular graphs with the same spectrum, but with different connectivity. [ABSTRACT FROM AUTHOR]

A mixed extension of a graph G is a graph H obtained from G by replacing each vertex of G by a clique or a coclique, where vertices of H coming from different vertices of G are adjacent if and only if the original vertices are adjacent in G. If G has no more than three vertices, H has all but at most three adjacency eigenvalues equal to 0 or − 1. In this paper we consider the converse problem, and determine the class G of all graphs with at most three eigenvalues unequal to 0 and − 1. Ignoring isolated vertices, we find that G consists of all mixed extensions of graphs on at most three vertices together with some particular mixed extensions of the paths P 4 and P 5. [ABSTRACT FROM AUTHOR]

A Deza graph with parameters (n,k,b,a) is a k‐regular graph with n vertices, in which any two vertices have a or b (a≤b) common neighbours. A Deza graph is strictly Deza if it has diameter 2, and is not strongly regular. In an earlier paper, the two last authors et al characterised the strictly Deza graphs with b=k−1 and β>1, where β is the number of vertices with b common neighbours with a given vertex. Here, we start with a characterisation of Deza graphs (not necessarily strictly Deza graphs) with parameters (n,k,k−1,0). Then, we deal with the case β=1 and a>0, and thus complete the characterisation of Deza graphs with b=k−1. It follows that all Deza graphs with b=k−1, β=1 and a>0 can be made from special strongly regular graphs, and in fact are strictly Deza except for K2. We present several examples of such strongly regular graphs. A divisible design graph (DDG) is a special Deza graph, and a Deza graph with β=1 is a DDG. The present characterisation reveals an error in a paper on DDGs by the second author et al. We discuss the cause and the consequences of this mistake and give the required errata. [ABSTRACT FROM AUTHOR]

A signed graph Γ is said to be determined by its spectrum if every signed graph with the same spectrum as Γ is switching isomorphic with Γ. Here it is proved that the path P n , interpreted as a signed graph, is determined by its spectrum if and only if n ≡ 0 , 1 , or 2 (mod 4), unless n ∈ { 8 , 13 , 14 , 17 , 29 } , or n = 3 . [ABSTRACT FROM AUTHOR]

We provide three infinite families of graphs in the Johnson and Grassmann schemes that are not uniquely determined by their spectrum. We do so by constructing graphs that are cospectral but non-isomorphic to these graphs. [ABSTRACT FROM AUTHOR]

Let n ≥ k ≥ 2 be two integers and S a subset of { 0 , 1 , … , k − 1 } . The graph J S ( n , k ) has as vertices the k -subsets of the n -set [ n ] = { 1 , … , n } and two k -subsets A and B are adjacent if | A ∩ B | ∈ S . In this paper, we use Godsil–McKay switching to prove that for m ≥ 0 , k ≥ max ⁡ ( m + 2 , 3 ) and S = { 0 , 1 , . . . , m } , the graphs J S ( 3 k − 2 m − 1 , k ) are not determined by spectrum and for m ≥ 2 , n ≥ 4 m + 2 and S = { 0 , 1 , . . . , m } the graphs J S ( n , 2 m + 1 ) are not determined by spectrum. We also report some computational searches for Godsil–McKay switching sets in the union of classes in the Johnson scheme for k ≤ 5 . [ABSTRACT FROM AUTHOR]

We investigate when a complete graph Kn with some edges deleted is determined by its adjacency spectrum. It is shown to be the case if the deleted edges form a matching, a complete graph Km provided m≤n-2, or a complete bipartite graph. If the edges of a path are deleted we prove that the graph is determined by its generalized spectrum (that is, the spectrum together with the spectrum of the complement). When at most five edges are deleted from Kn, there is just one pair of nonisomorphic cospectral graphs. We construct nonisomorphic cospectral graphs (with cospectral complements) for all n if six or more edges are deleted from Kn, provided that n is big enough. [ABSTRACT FROM AUTHOR]

Abstract: We study the energy per vertex in regular graphs. For every , we give an upper bound for the energy per vertex of a k-regular graph, and show that a graph attains the upper bound if and only if it is the disjoint union of incidence graphs of projective planes of order or, in case , the disjoint union of triangles and hexagons. For every k, we also construct k-regular subgraphs of incidence graphs of projective planes for which the energy per vertex is close to the upper bound. In this way, we show that this upper bound is asymptotically tight. [Copyright &y& Elsevier]

A Deza graph G with parameters (n , k , b , a) is a k -regular graph with n vertices such that any two distinct vertices have b or a common neighbours. The children G A and G B of a Deza graph G are defined on the vertex set of G such that every two distinct vertices are adjacent in G A or G B if and only if they have a or b common neighbours, respectively. A strongly Deza graph is a Deza graph with strongly regular children. In this paper we give a spectral characterisation of strongly Deza graphs, show relationships between eigenvalues, and study strongly Deza graphs which are distance-regular. [ABSTRACT FROM AUTHOR]

Abstract: We show that any connected regular graph with distinct eigenvalues and odd-girth is distance-regular, and in particular that it is a generalized odd graph. [Copyright &y& Elsevier]

Abstract: A divisible design graph is a graph whose adjacency matrix is the incidence matrix of a divisible design. Divisible design graphs are a natural generalization of -graphs, and like -graphs they make a link between combinatorial design theory and algebraic graph theory. The study of divisible design graphs benefits from, and contributes to, both parts. Using information of the eigenvalues of the adjacency matrix, we obtain necessary conditions for existence. Old results of Bose and Connor on symmetric divisible designs give other conditions and information on the structure. Many constructions are given using various combinatorial structures, such as -graphs, distance-regular graphs, symmetric divisible designs, Hadamard matrices, and symmetric balanced generalized weighing matrices. Several divisible design graphs are characterized in terms of the parameters. [ABSTRACT FROM AUTHOR]

Abstract: Using results on Hadamard difference sets, we construct regular graphical Hadamard matrices of negative type of order for every positive integer . If , such a Hadamard matrix is equivalent to a strongly regular graph with parameters . Strongly regular graphs with these parameters have been called max energy graphs, because they have maximal energy (as defined by Gutman) among all graphs on vertices. For odd the strongly regular graphs seem to be new. [Copyright &y& Elsevier]

Abstract: In [E.R. van Dam, W.H. Haemers, Which graphs are determined by their spectrum? Linear Algebra Appl. 373 (2003), 241–272] we gave a survey of answers to the question of which graphs are determined by the spectrum of some matrix associated to the graph. In particular, the usual adjacency matrix and the Laplacian matrix were addressed. Furthermore, we formulated some research questions on the topic. In the meantime, some of these questions have been (partially) answered. In the present paper we give a survey of these and other developments. [Copyright &y& Elsevier]

Abstract: The energy of a graph is the sum of the absolute values of the eigenvalues of its adjacency matrix. Koolen and Moulton have proved that the energy of a graph on n vertices is at most , and that equality holds if and only if the graph is strongly regular with parameters . Such graphs are equivalent to a certain type of Hadamard matrices. Here we survey constructions of these Hadamard matrices and the related strongly regular graphs. [Copyright &y& Elsevier]

Abstract: We show that if is the jth largest Laplacian eigenvalue, and is the jth largest degree of a connected graph on n vertices, then . This settles a conjecture due to Guo. [Copyright &y& Elsevier]

Abstract: The lollipop graph, denoted by , is obtained by appending a cycle to a pendant vertex of a path . We will show that no two non-isomorphic lollipop graphs are cospectral with respect to the adjacency matrix. It is proved that for p odd the lollipop graphs and some related graphs are determined by the adjacency spectrum, and that all lollipop graphs are determined by its Laplacian spectrum. [Copyright &y& Elsevier]

Abstract: In this paper, we begin the determination of all primitive strongly regular graphs with chromatic number equal to 5. Using eigenvalue techniques, we show that there are at most 43 possible parameter sets for such a graph. For each parameter set, we must decide which strongly regular graphs, if any, possessing the set are 5-chromatic. In this way, we deal completely with 34 of these parameter sets using eigenvalue techniques and computer enumerations. [Copyright &y& Elsevier]

Abstract: For every rational number x ∈(0,1), we construct a pair of graphs, one regular and one nonregular with adjacency matrices A 1 and A2, having the property that A 1 − xJ and A 2 − xJ have the same spectrum (J is the all-ones matrix). This solves a problem of Van Dam and the second author. For some values of x, we have generated the smallest examples (with respect to the number of vertices) by computer. [Copyright &y& Elsevier]

Abstract: We give sufficient conditions for existence of a perfect matching in a graph in terms of the eigenvalues of the Laplacian matrix. We also show that a distance-regular graph of degree k is k-edge-connected. [Copyright &y& Elsevier]

We have enumerated all graphs on at most 11 vertices and determined their spectra with respect to various matrices, such as the adjacency matrix and the Laplacian matrix. We have also counted the numbers for which there is at least one other graph with the same spectrum (a cospectral mate). In addition we consider a construction for pairs of cospectral graphs due to Godsil and McKay, which we call GM switching. It turns out that for the enumerated cases a large part of all cospectral graphs comes from GM switching, and that the fraction of graphs on n vertices with a cospectral mate starts to decrease at some value of n<11 (depending on the matrix). Since the fraction of cospectral graphs on n vertices constructible by GM switching tends to 0 if n→∞, the present data give some indication that possibly almost no graph has a cospectral mate. We also derive asymptotic lower bounds for the number of graphs with a cospectral mate from GM switching. [Copyright &y& Elsevier]

For almost all graphs the answer to the question in the title is still unknown. Here we survey the cases for which the answer is known. Not only the adjacency matrix, but also other types of matrices, such as the Laplacian matrix, are considered. [Copyright &y& Elsevier]

It is proved that a graph whose (0,1)-adjacency matrix has the spectrum of Pn, the complement of the path on n vertices, must be Pn. [Copyright &y& Elsevier]

The two-graph code of the Hermitian two-graph Hq is investigated. By use of this code we show that if q≡3 (mod 8) there exists no strongly regular graph with valency q2(q−1)/2 in the switching class corresponding to Hq. For q=5 the code is worked out in detail. We generate the weight enumerator and give an account for the code words of several weights. Here it follows that there is a unique regular graph with valency 50 in the switching class. [Copyright &y& Elsevier]

We study the behavior of the 2-rank of the adjacency matrix of a graph under Seidel and Godsil–McKay switching, and apply the result to graphs coming from graphical Hadamard matrices of order 4 m. Starting with graphs from known Hadamard matrices of order 64, we find (by computer) many Godsil–McKay switching sets that increase the 2-rank. Thus we find strongly regular graphs with parameters (63 , 32 , 16 , 16) , (64 , 36 , 20 , 20) , and (64 , 28 , 12 , 12) for almost all feasible 2-ranks. In addition we work out the behavior of the 2-rank for a graph product related to the Kronecker product for Hadamard matrices, which enables us to find many graphical Hadamard matrices of order 4 m for which the number of related strongly regular graphs with different 2-ranks is unbounded as a function of m. The paper extends results from the article 'Switched symplectic graphs and their 2-ranks' by the first and the last author. [ABSTRACT FROM AUTHOR]

The pineapple graph K p q is obtained by appending q pendant edges to a vertex of a complete graph K p (p ≥ 3 , q ≥ 1). We prove that among connected graphs, the pineapple graph is determined by its adjacency spectrum. Moreover, we determine all disconnected graphs which are cospectral with a pineapple graph. Thus we find for which values of p and q the pineapple graph K p q is determined by its adjacency spectrum. The main tool is a recent classification of all graphs with all but three eigenvalues equal to 0 or − 1 by the third author. [ABSTRACT FROM AUTHOR]

The pineapple graph K p q is obtained by appending q pendant edges to a vertex of a complete graph K p ( q ≥ 1 , p ≥ 3 ). Zhang and Zhang (2009) [7] claim that the pineapple graphs are determined by their adjacency spectrum. We show that their claim is false by constructing graphs which are cospectral and non-isomorphic with K p q for every p ≥ 4 and various values of q . In addition we prove that the claim is true if q = 2 , and refer to the literature for q = 1 , p = 3 , and ( p , q ) = ( 4 , 3 ) . [ABSTRACT FROM AUTHOR]

Abstract: Let G be a connected k-regular graph of order n. We find a best upper bound (in terms of k) on the third largest eigenvalue that is sufficient to guarantee that G has a perfect matching when n is even, and a matching of order when n is odd. We also examine how other eigenvalues affect the size of matchings in G. [Copyright &y& Elsevier]

For each b ≥ 5 we construct a pair of cospectral b -regular graphs, where one has a perfect matching and the other one not. This solves a research problem posed by the third author at the 22nd British Combinatorial Conference. [ABSTRACT FROM AUTHOR]