Search

We consider signed graphs with just 2 or 3 distinct eigenvalues, in particular (i) those with at least one simple eigenvalue, and (ii) those with vertex-deleted subgraphs which themselves have at most 3 distinct eigenvalues. We also construct new examples using weighing matrices and symmetric 3-class association schemes.

In this paper, we discuss various connections between the smallest eigenvalue of the adjacency matrix of a graph and its structure. There are several techniques for obtaining upper bounds on the smallest eigenvalue, and some of them are based on Rayleigh quotients, Cauchy interlacing using induced subgraphs, and Haemers interlacing with vertex partitions and quotient matrices. In this paper, we are interested in obtaining lower bounds for the smallest eigenvalue. Motivated by results on line graphs and generalized line graphs, we show how graph decompositions can be used to obtain such lower bounds.

In this paper our focus is on regular signed graphs with exactly 3 (distinct) eigenvalues. We establish certain basic results; for example, we show that they are walk-regular. We also give some constructions and determine all the signed graphs with 3 eigenvalues, under the constraint that they are either signed line graphs or have vertex degree 3. We also report our result of computer search on those with at most 10 vertices.

Graphs G and H are called cospectral if they have the same characteristic polynomial. If eigenvalues are integral, then corresponding graphs are called integral graph. In this article we introduce a construction to produce pairs of cospectral integral regular graphs. Generalizing the construction of G4(a, b) and G5(a, b) due to Wang and Sun, we define graphs 𝒢4(G,H) and 𝒢5(G,H) and show that they are cospectral integral regular when G is an integral q-regular graph of order m and H is an integral q-regular graph of order (b − 2)m for some integer b ≥ 3.

A graph in a certain graph class is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum among all graphs in that class. Bell et al. have identified a subclass within the connected graphs of order n and size m in which minimizing graphs belong (the complements of such graphs are either disconnected or contain a clique of size n/2 ). In this paper we discuss the minimizing graphs of a special class of graphs of order n whose complements are connected and contains exactly one cycle (namely the class Ucn of graphs whose complements are unicyclic), and characterize the unique minimizing graph in Ucn when n ≥ 20.

Let G = G1 ∪ G2 be the sum of two simple graphs G1,G2 having a common edge or G = G1 ∪ e1 ∪ e2 ∪ G2 be the sum of two simple disjoint graphs G1,G2 connected by two edges e1 and e2 which form a cycle C4 inside G. We give a method of computing the determinant det A(G) of the adjacency matrix of G by reducing the calculation of the determinant to certain subgraphs of G1 and G2. To show the scope and effectiveness of our method we give some examples

The main eigenvalues of a graph G are those eigenvalues of the (0; 1)- adjacency matrix A with a corresponding eigenspace not orthogonal to j = (1 /1/ ... j 1)T. The principal main eigenvector associated with a main eigenvalue is the orthogonal projection of the corresponding eigenspace onto j. The main eigenspace of a graph is generated by all the principal main eigenvectors and is the same as the image of the walk matrix. We explore a new concept to see to what extent the main eigenspace determines the entries of the walk matrix of a graph. The CDC of a graph G is the direct product G x K2. We establish a hierarchy of inclusions connecting classes of graphs in view of their CDC, walk matrix, main eigenvalues and main eigenspaces. We provide a new proof that graphs with the same CDC are characterized as TF-isomorphic graphs. A complete list of TF-isomorphic graphs on at most 8 vertices and their common CDC is also given. [ABSTRACT FROM AUTHOR]

Twin vertices of a graph have the same open neighbourhood. If they are not adjacent, then they are called duplicates and contribute the eigenvalue zero to the adjacency matrix. Otherwise they are termed co-duplicates, when they contribute -1 as an eigenvalue of the adjacency matrix. On removing a twin vertex from a graph, the spectrum of the adjacency matrix does not only lose the eigenvalue 0 or -1. The perturbation sends a rippling effect to the spectrum. The simple eigenvalues are displaced. We obtain a closed formula for the characteristic polynomial of a graph with twin vertices in terms of two polynomials associated with the perturbed graph. These are used to obtain estimates of the displacements in the spectrum caused by the perturbation. [ABSTRACT FROM AUTHOR]

A signed graph has edge weights drawn from the set {+1, -1}, and is sign-balanced if it is equivalent to an unsigned graph under the operation of sign switching; otherwise it is sign-unbalanced. A nut graph has a one dimensional kernel of the 0-1 adjacency matrix with a corresponding eigenvector that is full. In this paper we generalise the notion of nut graphs to signed graphs. Orders for which regular nut graphs with all edge weights +1 exist have been determined recently for the degrees up to 12. By extending the definition to signed graphs, we here find all pairs (ρ, n) for which a ρ-regular nut graph (sign-balanced or sign-unbalanced) of order n exists with ρ ≤ 11. We devise a construction for signed nut graphs based on a smaller 'seed' graph, giving infinite series of both sign-balanced and sign-unbalanced ρ-regular nut graphs. Orders for which a regular nut graph with ρ = n - 1 exists are characterised; they are sign-unbalanced with an underlying graph Kn for which n ≡ 1 (mod 4). Orders for which a regular sign-unbalanced nut graph with ρ = n-2 exists are also characterised; they have an underlying cocktail-party graph CP(n) with even order n ≥ 8. [ABSTRACT FROM AUTHOR]

Given a signed graph Ġ, let A Ġ and D± Ġ denote its standard adjacency matrix and the diagonal matrix of vertex net-degrees, respectively. The net Laplacian matrix of Ġ is defined to be NĠ = D± Ġ -AĠ. In this study we give some properties of the eigenvalues of NĠ. In particular, we consider their behaviour under some edge perturbations, establish some relations between them and the eigenvalues of the standard Laplacian matrix and give some lower and upper bounds for the largest eigenvalue of NĠ. [ABSTRACT FROM AUTHOR]

The eigenvalues of a graph are those of its adjacency matrix. Recently, Cioabă, Haemers and Vermette characterized all graphs with all but two eigenvalues equal to -2 and 0. In this article, we extend their result by characterizing explicitly all graphs with all but two eigenvalues in the interval [-2, 0]. Also, we determine among them those that are determined by their spectrum. [ABSTRACT FROM AUTHOR]

Let Γ = (G, σ) be a signed graph, where G is the underlying simple graph and σ : E(G) → {--, +} is the sign function on the edges of G. The adjacency matrix of a signed graph has -1 or +1 for adjacent vertices, depending on the sign of the edges. It was conjectured that if Γ is a signed complete graph of order n with k negative edges, k < n -- 1 and Γ has maximum index, then negative edges form K1,k. In this paper, we prove this conjecture if we confine ourselves to all signed complete graphs of order n whose negative edges form a tree of order k + 1. A [1, 2]-subgraph of G is a graph whose components are paths and cycles. Let Γ be a signed complete graph whose negative edges form a [1, 2]-subgraph. We show that the eigenvalues of Γ satisfy the following inequalities: --5 ≤ λn ≤ ... ≤ λ2 ≤ 3. [ABSTRACT FROM AUTHOR]

Let A(G) and D(G) be the adjacency matrix and the degree matrix of a graph G, respectively. For any real α ∊ [0,1], we consider Aα(G) = αD(G) + (1 -- α)A(G) as a graph matrix, whose largest eigenvalue is called the Aα-spectral radius of G. We first show that the smallest limit point for the Aα-spectral radius of graphs is 2, and then we characterize the connected graphs whose Aα-spectral radius is at most 2. Finally, we show that all such graphs, with four exceptions, are determined by their Aα-spectra. [ABSTRACT FROM AUTHOR]

The complementary spectrum of a connected graph G is the set of the complementary eigenvalues of the adjacency matrix of G. In this note, we discuss the possibility of representing G using this spectrum. On one hand, we give evidence that this spectrum distinguishes more graphs than other standard graph spectra. On the other hand, we show that it is hard to compute the complementary spectrum. In particular, we see that computing the complementary spectrum is equivalent to finding all connected induced subgraphs. [ABSTRACT FROM AUTHOR]

Let G be a graph with m edges and let ρ be the largest eigenvalue of its adjacency matrix. It is shown that...improving the well-known bound of Stanley. Moreover, writing ω for the clique number of G and Wk for the number of its walks on k vertices, it is shown that the sequence...is nonincreasing and converges to ρ. [ABSTRACT FROM AUTHOR]

Given a graph G, its adjacency matrix A(G) and its diagonal matrix of vertex degrees D(G) consider the matrix Aα(G) = αD(G) + (1 -- α)A(G), where α ∊ [0,1). The Aα-spectrum of G is the multiset of eigenvalues of Aα(G) and these eigenvalues are the α-eigenvalues of G. A cluster in G is a pair of vertex subsets (C, S), where C is a set of cardinality |C| ≥ 2 of pairwise co-neighbor vertices sharing the same set S of |S| neighbors. Assuming that G is connected and it has a cluster (C, S), G(H) is obtained from G and an r-regular graph H of order |C| by identifying its vertices with the vertices in C, eigenvalues of Aα(G) and Aα(G(H)) are deduced and if Aα(H) is positive semidefinite, then the i-th eigenvalue of Aα(G(H)) is greater than or equal to i-th eigenvalue of Aα(G). These results are extended to graphs with several pairwise disjoint clusters (C1, S1), .. ., (Ck, Sk). As an application, the effect on the energy, α-Estrada index and α-index of a graph G with clusters when the edges of regular graphs are added to G are analyzed. Finally, the Aα-spectrum of the corona product G o H of a connected graph G and a regular graph H is determined. [ABSTRACT FROM AUTHOR]

One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to Alan Hoffman, where μ1 and μn are respectively the maximum and minimum eigenvalues of the adjacency matrix: χ ≥ 1+μ1/−μn. We recently generalised this bound to include all eigenvalues of the adjacency matrix.

The energy of a molecular graph G is defined as the summation of the absolute values of the eigenvalues of adjacency matrix of a graph G. In this paper, an infinite class of fullerene graphs with 10n vertices, n ≥ 2, is considered. By proving centrosymmetricity of the adjacency matrix of these fullerene graphs, a lower bound for its energy is given. Our method is general and can be extended to other class of fullerene graphs. [ABSTRACT FROM AUTHOR]

When a graceful labeling of a bipartite graph places the smaller labels in one of the stable sets of the graph, it becomes an α-labeling. This is the most restrictive type of difference-vertex labeling and it is located at the very core of this research area. Here we use an extension of the adjacency matrix to count and classify α-labeled graphs according to their size, order, and boundary value. [ABSTRACT FROM AUTHOR]

Several matrices can be associated to a graph, such as the adjacency matrix or the Laplacian matrix. The spectrum of these matrices gives some informations about the structure of the graph and the question "Which graphs are determined by their spectrum?" is still a difficult problem in spectral graph theory. Let U2qp be the set of graphs obtained from Cp by attaching two pendant edges to each of q (q ≤ p) vertices on Cp, whereas V2qp the subset of U2qp with odd p and its q vertices of degree 4 being nonadjacent to each other. In this paper, we show that each graph in U 2q p , p even and its q vertices of degree 4 being consecutive, is determined by its Laplacian spectrum. As well we show that if G is a graph without isolated vertices and adjacency cospectral with the graph in Vp-1p = {H}, then G ≃= H. [ABSTRACT FROM AUTHOR]

Given a graph G, its adjacency matrix A(G) and its diagonal matrix of vertex degrees D(G), consider the matrix Aα (G) = αD(G) + (1 − α)A(G), where α ∈ [0, 1). The Aα -spectrum of G is the multiset of eigenvalues of Aα (G) and these eigenvalues are the α-eigenvalues of G. A cluster in G is a pair of vertex subsets (C, S), where C is a set of cardinality |C| ≥ 2 of pairwise co-neighbor vertices sharing the same set S of |S| neighbors. Assuming that G is connected and it has a cluster (C, S), G(H) is obtained from G and an r-regular graph H of order |C| by identifying its vertices with the vertices in C, eigenvalues of Aα (G) and Aα (G(H)) are deduced and if Aα (H) is positive semidefinite, then the i-th eigenvalue of Aα (G(H)) is greater than or equal to i-th eigenvalue of Aα (G). These results are extended to graphs with several pairwise disjoint clusters (C1, S1), . . . , (Ck, Sk). As an application, the effect on the energy, α-Estrada index and α-index of a graph G with clusters when the edges of regular graphs are added to G are analyzed. Finally, the Aα-spectrum of the corona product G ◦ H of a connected graph G and a regular graph H is determined.

Let A(G) and D(G) be the adjacency matrix and the degree matrix of a graph G, respectively. For any real α ∈ [0, 1], we consider Aα (G) = αD(G) + (1 − α)A(G) as a graph matrix, whose largest eigenvalue is called the Aα -spectral radius of G. We first show that the smallest limit point for the Aα -spectral radius of graphs is 2, and then we characterize the connected graphs whose Aα -spectral radius is at most 2. Finally, we show that all such graphs, with four exceptions, are determined by their Aα -spectra.

Several matrices can be associated to a graph, such as the adjacency matrix or the Laplacian matrix. The spectrum of these matrices gives some informations about the structure of the graph and the question “Which graphs are determined by their spectrum?” is still a difficult problem in spectral graph theory. Let 𝒰p2q${\cal U}_p^{2q}$ be the set of graphs obtained from Cp by attaching two pendant edges to each of q (q ⩽ p) vertices on Cp, whereas 𝒱p2q${\cal V}_p^{2q}$ the subset of 𝒰p2q${\cal U}_p^{2q}$ with odd p and its q vertices of degree 4 being nonadjacent to each other. In this paper, we show that each graph in 𝒰p2q${\cal U}_p^{2q}$ , p even and its q vertices of degree 4 being consecutive, is determined by its Laplacian spectrum. As well we show that if G is a graph without isolated vertices and adjacency cospectral with the graph in 𝒱pp−1={H}${\cal V}_p^{p - 1} = \{ H\}$ , then G ≅ H.