There are exactly 172 connected integral graphs up to 10 vertices.
Thin Lehman matrices and their graphs.
Threshold functions for the bipartite Turán property.
Tight bounds on the algebraic connectivity of a balanced binary tree.
Tight estimates for eigenvalues of regular graphs.
Totally positive completions for monotonically labeled block clique graphs.
TOWARDS A SPECTRAL THEORY OF GRAPHS BASED ON THE SIGNLESS LAPLACIAN, I
Tricyclic graphs with exactly two main eigenvalues
An eigenvalue of a graph G is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. Let G 0 be the graph obtained from G by deleting all pendant vertices and δ(G) the minimum degree of vertices of G. In this paper, all connected tricyclic graphs G with δ(G 0) ≥ 2 and exactly two main eigenvalues are determined.
Tridiagonal matrices and spectral properties of some graph classes
A graph is called a chain graph if it is bipartite and the neighbourhoods of the vertices in each colour class form a chain with respect to inclusion. In this paper we give an explicit formula for the characteristic polynomial of any chain graph and we show that it can be expressed using the determinant of a particular tridiagonal matrix. Then this fact is applied to show that in a certain interval a chain graph does not have any nonzero eigenvalue. A similar result is provided for threshold graphs....
Two Graphs with a Common Edge
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
Unbalanced unicyclic and bicyclic graphs with extremal spectral radius
A signed graph is a graph whose edges are labeled by signs. If has vertices, its spectral radius is the number , where are the eigenvalues of the signed adjacency matrix . Here we determine the signed graphs achieving the minimal or the maximal spectral radius in the classes and of unbalanced unicyclic graphs and unbalanced bicyclic graphs, respectively.
Unicyclic graphs with bicyclic inverses
A graph is nonsingular if its adjacency matrix is nonsingular. The inverse of a nonsingular graph is a graph whose adjacency matrix is similar to via a particular type of similarity. Let denote the class of connected bipartite graphs with unique perfect matchings. Tifenbach and Kirkland (2009) characterized the unicyclic graphs in which possess unicyclic inverses. We present a characterization of unicyclic graphs in which possess bicyclic inverses.
Unicyclic graphs with the strong reciprocal eigenvalue property.
Unified Spectral Bounds on the Chromatic Number
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. In this paper, we further generalize these results to include all eigenvalues of the adjacency, Laplacian and signless Laplacian matrices. The various known bounds are also unified...
Universally optimal matrices and field independence of the minimum rank of a graph.
Upper bound for the energy of graphs with fixed second and fourth spectral moments
Upper bound for the non-maximal eigenvalues of irreducible nonnegative matrices
We present a lower and an upper bound for the second smallest eigenvalue of Laplacian matrices in terms of the averaged minimal cut of weighted graphs. This is used to obtain an upper bound for the real parts of the non-maximal eigenvalues of irreducible nonnegative matrices. The result can be applied to Markov chains.
Variable neighborhood search for extremal graphs. 17. Further conjectures and results about the index
The AutoGraphiX 2 system is used to compare the index of a connected graph G with a number of other graph theoretical invariants, i.e., chromatic number, maximum, minimum and average degree, diameter, radius, average distance, independence and domination numbers. In each case, best possible lower and upper bounds, in terms of the order of G, are sought for sums, differences, ratios and products of the index and another invariant. There are 72 cases altogether: in 7 cases known results were reproduced,...
Visibility Graphs of Staircase Polygons and the Weak Bruhat Order, I: from Visibility Graphs to Maximal Chains.
Weighted matrix eigenvalue bounds on the independence number of a graph.