On the adjacency matrix of a threshold graph

A threshold graph on n   vertices is coded by a binary string of length n−1$n-1$. We obtain a formula for the inertia of (the adjacency matrix of) a threshold graph in terms of the code of the graph. It is shown that the number of negative eigenvalues of the adjacency matrix of a threshold graph is the number of ones in the code, whereas the nullity is given by the number of zeros in the code that are preceded by either a zero or a blank. A formula for the determinant of the adjacency matrix of a generalized threshold graph and the inverse, when it exists, of the adjacency matrix of a threshold graph are obtained. Results for antiregular graphs follow as special cases.     

An edge grafting theorem on the energy of unicyclic and bipartite graphs

The energy of a graph is the sum of the absolute values of the eigenvalues of its adjacency matrix. The edge grafting operation on a graph is certain kind of edge moving between two pendant paths starting from the same vertex. In this paper we show how the graph energy changes under the edge grafting operations on unicyclic and bipartite graphs. We also give some applications of this result on the comparison of graph energies between unicyclic or bipartite graphs.     

On the null-spaces of acyclic and unicyclic singular graphs

For acyclic and unicyclic graphs we determine a necessary and sufficient condition for a graph G to be singular. Further, it is shown that this characterization can be used to construct a basis for the null-space of G.     

The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample

Let G be an undirected graph on n vertices and let S(G) be the set of all real symmetric n×n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The inverse inertia problem for G asks which inertias can be attained by a matrix in S(G). We give a complete answer to this question for trees in terms of a new family of graph parameters, the maximal disconnection numbers of a graph. We also give a formula for the inertia set of a graph with a cut vertex in terms of inertia sets of proper subgraphs. Finally, we give an example of a graph that is not inertia-balanced, which settles an open problem from the October 2006 AIM Workshop on Spectra of Families of Matrices described by Graphs, Digraphs and Sign Patterns. We also determine some restrictions on the inertia set of any graph.     

Trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues

The signless Laplacian matrix of a graph G is defined to be the sum of its adjacency matrix and degree diagonal matrix, and its eigenvalues are called Q-eigenvalues of G. A Q-eigenvalue of a graph G is called a Q-main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. In this work, all trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues are determined.     

The Laplacian spread of quasi-tree graphs

The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second-smallest eigenvalue of the Laplacian matrix of the graph. Bao, Tan and Fan [Y.H. Bao, Y.Y. Tan,Y.Z. Fan, The Laplacian spread of unicyclic graphs, Appl. Math. Lett. 22 (2009) 1011-1015.] characterize the unique unicyclic graph with maximum Laplacian spread among all connected unicyclic graphs of fixed order. In this paper, we characterize the unique quasi-tree graph with maximum Laplacian spread among all quasi-tree graphs in the set Q(n,d) with .     

On the nullity of graphs with pendent vertices

The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. Cheng and Liu [B. Cheng, B. Liu, On the nullity of graphs, Electron. J. Linear Algebra 16 (2007) 60-67] characterized the extremal graphs attaining the upper bound n-2 and the second upper bound n-3. In this paper, as the continuance of it, we determine the extremal graphs with pendent vertices achieving the third upper bound n-4 and fourth upper bound n-5. We then proceed recursively to construct all graphs with pendent vertices which satisfy η(G)>0. Our results provide a unified approach to determine n-vertex unicyclic (respectively, bicyclic and tricyclic) graphs which achieve the maximal and second maximal nullity and characterize n-vertex extremal trees attaining the second and third maximal nullity. As a consequence we, respectively, determine the nullity sets of trees, unicyclic graphs, bicyclic graphs and tricyclic graphs on n vertices.     

Distance spectra and distance energy of integral circulant graphs

The distance energy of a graph G is a recently developed energy-type invariant, defined as the sum of absolute values of the eigenvalues of the distance matrix of G. There was a vast research for the pairs and families of non-cospectral graphs having equal distance energy, and most of these constructions were based on the join of graphs. A graph is called circulant if it is Cayley graph on the circulant group, i.e. its adjacency matrix is circulant. A graph is called integral if all eigenvalues of its adjacency matrix are integers. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer. In this paper, we characterize the distance spectra of integral circulant graphs and prove that these graphs have integral eigenvalues of distance matrix D. Furthermore, we calculate the distance spectra and distance energy of unitary Cayley graphs. In conclusion, we present two families of pairs (G₁,G₂) of integral circulant graphs with equal distance energy - in the first family G₁ is subgraph of G₂, while in the second family the diameter of both graphs is three.     

On incidence energy of a graph

The Laplacian-energy like invariant LEL(G) and the incidence energy IE(G) of a graph are recently proposed quantities, equal, respectively, to the sum of the square roots of the Laplacian eigenvalues, and the sum of the singular values of the incidence matrix of the graph G. However, IE(G) is closely related with the eigenvalues of the Laplacian and signless Laplacian matrices of G. For bipartite graphs, IE=LEL. We now point out some further relations for IE and LEL: IE can be expressed in terms of eigenvalues of the line graph, whereas LEL in terms of singular values of the incidence matrix of a directed graph. Several lower and upper bounds for IE are obtained, including those that pertain to the line graph of G. In addition, Nordhaus-Gaddum-type results for IE are established.     

On the nullity and the matching number of unicyclic graphs

Let G be a graph with n vertices and ν(G) be the matching number of G. Let η(G) denote the nullity of G (the multiplicity of the eigenvalue zero of G). It is well known that if G is a tree, then η(G)=n-2ν(G). Tan and Liu [X. Tan, B. Liu, On the nullity of unicyclic graphs, Linear Alg. Appl. 408 (2005) 212-220] proved that the nullity set of all unicyclic graphs with n vertices is {0,1,…,n-4} and characterized the unicyclic graphs with η(G)=n-4. In this paper, we characterize the unicyclic graphs with η(G)=n-5, and we prove that if G is a unicyclic graph, then η(G) equals , or n-2ν(G)+2. We also give a characterization of these three types of graphs. Furthermore, we determine the unicyclic graphs G with η(G)=0, which answers affirmatively an open problem by Tan and Liu.     

Addressing the Petersen graph

Motivated by a problem on message routing in communication networks, Graham and Pollak proposed a scheme for addressing the vertices of a graph G by N-tuples of three symbols in such a way that distances between vertices may readily be determined from their addresses. They observed that N?h(D), the maximum of the number of positive and the number of negative eigenvalues of the distance matrix D of G. A result of Gregory, Shader and Watts yields a necessary condition for equality to occur. As an illustration, we show that N>h(D)=5 for all addressings of the Petersen graph and then give an optimal addressing by 6-tuples.     

Two spectral characterizations of regular, bipartite graphs with five eigenvalues

Graphs with a few distinct eigenvalues usually possess an interesting combinatorial structure. We show that regular, bipartite graphs with at most six distinct eigenvalues have the property that each vertex belongs to the constant number of quadrangles. This enables to determine, from the spectrum alone, the feasible families of numbers of common neighbors for each vertex with other vertices in its part. For particular spectra, such as [6,2⁹,0⁶,-2⁹,-6] (where exponents denote eigenvalue multiplicities), there is a unique such family, which makes it possible to characterize all graphs with this spectrum.Using this lemma we also to show that, for r?2, a graph has spectrum if and only if it is a graph of a 1-resolvable transversal design TD(r,r), i.e., if it corresponds to the complete set of mutually orthogonal Latin squares of size r in a well-defined manner.     

On acyclic and unicyclic graphs whose minimum rank equals the diameter

The minimum rank of a graph G is defined as the smallest possible rank over all symmetric matrices governed by G. It is well known that the minimum rank of a connected graph is at least the diameter of that graph. In this paper, we investigate the graphs for which equality holds between minimum rank and diameter, and completely describe the acyclic and unicyclic graphs for which this equality holds.     

On the Szeged and the Laplacian Szeged spectrum of a graph

For a given graph G its Szeged weighting is defined by w(e)=n_u(e)n_v(e), where e=uv is an edge of G,n_u(e) is the number of vertices of G closer to u than to v, and n_v(e) is defined analogously. The adjacency matrix of a graph weighted in this way is called its Szeged matrix. In this paper we determine the spectra of Szeged matrices and their Laplacians for several families of graphs. We also present sharp upper and lower bounds on the eigenvalues of Szeged matrices of graphs.     

On the Estrada and Laplacian Estrada indices of graphs

The Estrada index of a graph G is defined as , where λ₁,λ₂,…,λ_n are the eigenvalues of G. The Laplacian Estrada index of a graph G is defined as , where μ₁,μ₂,…,μ_n are the Laplacian eigenvalues of G. An edge grafting operation on a graph moves a pendent edge between two pendent paths. We study the change of Estrada index of graph under edge grafting operation between two pendent paths at two adjacent vertices. As the application, we give the result on the change of Laplacian Estrada index of bipartite graph under edge grafting operation between two pendent paths at the same vertex. We also determine the unique tree with minimum Laplacian Estrada index among the set of trees with given maximum degree, and the unique trees with maximum Laplacian Estrada indices among the set of trees with given diameter, number of pendent vertices, matching number, independence number and domination number, respectively.     

Complete solution to a problem on the maximal energy of unicyclic bipartite graphs

The energy of a simple graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Denote by C_n the cycle, and the unicyclic graph obtained by connecting a vertex of C₆ with a leaf of P_n-6. Caporossi et al. conjectured that the unicyclic graph with maximal energy is for n=8,12,14 and n≥16. In Hou et al. (2002) [Y. Hou, I. Gutman, C. Woo, Unicyclic graphs with maximal energy, Linear Algebra Appl. 356 (2002) 27-36], the authors proved that is maximal within the class of the unicyclic bipartite n-vertex graphs differing from C_n. And they also claimed that the energies of C_n and is quasi-order incomparable and left this as an open problem. In this paper, by utilizing the Coulson integral formula and some knowledge of real analysis, especially by employing certain combinatorial techniques, we show that the energy of is greater than that of C_n for n=8,12,14 and n≥16, which completely solves this open problem and partially solves the above conjecture.     

The integral graphs with index 3 and exactly two main eigenvalues

A graph is called integral if the spectrum of its adjacency matrix has only integral eigenvalues. An eigenvalue of a graph is called main eigenvalue if it has an eigenvector such that the sum of whose entries is not equal to zero. In this paper, we show that there are exactly 25 connected integral graphs with exactly two main eigenvalues and index 3.     

Estimating the Estrada index

Let G be a graph on n vertices, and let λ₁,λ₂,…,λ_n be its eigenvalues. The Estrada index of G is a recently introduced graph invariant, defined as . We establish lower and upper bounds for EE in terms of the number of vertices and number of edges. Also some inequalities between EE and the energy of G are obtained.     

On encodings of spanning trees

Deo and Micikevicius recently gave a new bijection for spanning trees of complete bipartite graphs. In this paper we devise a generalization of Deo and Micikevicius's method, which is also a modification of Olah's method for encoding the spanning trees of any complete multipartite graph K(n₁,…,n_r). We also give a bijection between the spanning trees of a planar graph and those of any of its planar duals. Finally we discuss the possibility of bijections for spanning trees of DeBriujn graphs, cubes, and regular graphs such as the Petersen graph that have integer eigenvalues.     

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.