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 energy of random graphs

In 1970s, Gutman introduced the concept of the energy E(G) for a simple graph G, which is defined as the sum of the absolute values of the eigenvalues of G. This graph invariant has attracted much attention, and many lower and upper bounds have been established for some classes of graphs among which bipartite graphs are of particular interest. But there are only a few graphs attaining the equalities of those bounds. We however obtain an exact estimate of the energy for almost all graphs by Wigner’s semi-circle law, which generalizes a result of Nikiforov. We further investigate the energy of random multipartite graphs by considering a generalization of Wigner matrix, and obtain some estimates of the energy for random multipartite graphs.     

On the maximal energy tree with two maximum degree vertices

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacent matrix.For Δ?3 and t?3, denote by T_a(Δ,t) (or simply T_a) the tree formed from a path P_t on t vertices by attaching Δ-1P₂’s on each end of the path P_t, and T_b(Δ,t) (or simply T_b) the tree formed from P_t+2 by attaching Δ-1P₂’s on an end of the P_t+2 and Δ-2P₂’s on the vertex next to the end.In Li et al.(2009) [16] proved that among trees of order n with two vertices of maximum degree Δ, the maximal energy tree is either the graph T_a or the graph T_b, where t=n+4-4Δ?3.However, they could not determine which one of T_a and T_b is the maximal energy tree.This is because the quasi-order method is invalid for comparing their energies.In this paper, we use a new method to determine the maximal energy tree.It turns out that things are more complicated.We prove that the maximal energy tree is T_b for Δ?7 and any t?3, while the maximal energy tree is T_a for Δ=3 and any t?3.Moreover, for Δ=4, the maximal energy tree is T_a for all t?3 but one exception that t=4, for which T_b is the maximal energy tree.For Δ=5, the maximal energy tree is T_b for all t?3 but 44 exceptions that t is both odd and 3?t?89, for which T_a is the maximal energy tree.For Δ=6, the maximal energy tree is T_b for all t?3 but three exceptions that t=3,5,7, for which T_a is the maximal energy tree.One can see that for most cases of Δ, T_b is the maximal energy tree,Δ=5 is a turning point, and Δ=3 and 4 are exceptional cases, which means that for all chemical trees (whose maximum degrees are at most 4) with two vertices of maximum degree at least 3, T_a has maximal energy, with only one exception T_a(4,4).     

Unicyclic graphs with large energy

We study the energy (i.e., the sum of the absolute values of all eigenvalues) of so-called tadpole graphs, which are obtained by joining a vertex of a cycle to one of the ends of a path. By means of the Coulson integral formula and careful estimation of the resulting integrals, we prove two conjectures on the largest and second-largest energy of a unicyclic graph due to Caporossi, Cvetkovi?, Gutman and Hansen and Gutman, Furtula and Hua, respectively. Moreover, we characterise the non-bipartite unicyclic graphs whose energy is largest.     

Solution to a conjecture on the maximal energy of bipartite bicyclic 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. Let C_n denote the cycle of order n and the graph obtained from joining two cycles C₆ by a path P_n-12 with its two leaves. Let B_n denote the class of all bipartite bicyclic graphs but not the graph R_a,b, which is obtained from joining two cycles C_a and C_b (a,b≥10 and ) by an edge. In [I. Gutman, D. Vidovi?, Quest for molecular graphs with maximal energy: a computer experiment, J. Chem. Inf. Sci. 41(2001) 1002-1005], Gutman and Vidovi? conjectured that the bicyclic graph with maximal energy is , for n=14 and n≥16. In [X. Li, J. Zhang, On bicyclic graphs with maximal energy, Linear Algebra Appl. 427(2007) 87-98], Li and Zhang showed that the conjecture is true for graphs in the class B_n. However, they could not determine which of the two graphs R_a,b and has the maximal value of energy. In [B. Furtula, S. Radenkovi?, I. Gutman, Bicyclic molecular graphs with the greatest energy, J. Serb. Chem. Soc. 73(4)(2008) 431-433], numerical computations up to a+b=50 were reported, supporting the conjecture. So, it is still necessary to have a mathematical proof to this conjecture. This paper is to show that the energy of is larger than that of R_a,b, which proves the conjecture for bipartite bicyclic graphs. For non-bipartite bicyclic graphs, the conjecture is still open.     

The Laplacian incidence energy of graphs

The Laplacian incidence energy of a graph is defined as the sum of the singular values of its normalized oriented incidence matrix. In this paper, we give sharp upper and lower bounds as well as the Coulson integral formula for the Laplacian incidence energy. Moreover, we show a close relation of the Laplacian incidence energy, normalized incidence energy and Randi? energy.     

Characterization of graphs having extremal Randi? indices

The higher Randi? index R_t(G) of a simple graph G is defined as

     

Laplacian energy of a graph

Let G be a graph with n vertices and m edges. Let λ₁, λ₂, … , λ_n be the eigenvalues of the adjacency matrix of G, and let μ₁, μ₂, … , μ_n be the eigenvalues of the Laplacian matrix of G. An earlier much studied quantity is the energy of the graph G. We now define and investigate the Laplacian energy as . There is a great deal of analogy between the properties of E(G) and LE(G), but also some significant differences.     

Lower bounds for the energy of digraphs

The energy of a digraph D is defined as , where z₁,…,z_n are the eigenvalues of D. In this article we find lower bounds for the energy of digraphs in terms of the number of closed walks of length 2, extending in this way the result obtained by Caporossi et al. [G. Caporossi, D. Cvetkovi?, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with extremal energy, J. Chem. Inf. Comput. Sci. 39 (1999) 984-996]: for all graphs G with m edges. Also, we study digraphs with three eigenvalues.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

Bounds on the eigenvalues of graphs with cut vertices or edges

In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n vertices and k cut edges. We also present lower bounds on the least eigenvalue in terms of the number of cut vertices or cut edges and upper bounds on the Laplacian spectral radius in terms of the number of cut vertices.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

Nowhere-zero eigenvectors of graphs

A vector is called nowhere-zero if it has no zero entry. In this article we search for graphs with nowhere-zero eigenvectors. We prove that distance-regular graphs and vertex-transitive graphs have nowhere-zero eigenvectors for all of their eigenvalues and edge-transitive graphs have nowhere-zero eigenvectors for all non-zero eigenvalues. Among other results, it is shown that a graph with three distinct eigenvalues has a nowhere-zero eigenvector for its smallest eigenvalue.     

On the nullity of graphs with pendant trees

The nullity of a graph is defined as the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. We investigate a class of graphs with pendant trees, and express the nullity of such graph in terms of that of its subgraphs. As an application of our results, we characterize unicyclic graphs with a given nullity.     

On Hadamard diagonalizable graphs

Of interest here is a characterization of the undirected graphs G such that the Laplacian matrix associated with G can be diagonalized by some Hadamard matrix. Many interesting and fundamental properties are presented for such graphs along with a partial characterization of the cographs that have this property.     

Constructably Laplacian integral graphs

A graph is Laplacian integral if the spectrum of its Laplacian matrix consists entirely of integers. We consider the class of constructably Laplacian integral graphs - those graphs that be constructed from an empty graph by adding a sequence of edges in such a way that each time a new edge is added, the resulting graph is Laplacian integral. We characterize the constructably Laplacian integral graphs in terms of certain forbidden vertex-induced subgraphs, and consider the number of nonisomorphic Laplacian integral graphs that can be constructed by adding a suitable edge to a constructably Laplacian integral graph. We also discuss the eigenvalues of constructably Laplacian integral graphs, and identify families of isospectral nonisomorphic graphs within the class.     

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 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.     

On the signless Laplacian spectral radius of graphs with cut vertices

In this paper, we show that among all the connected graphs with n vertices and k cut vertices, the maximal signless Laplacian spectral radius is attained uniquely at the graph G_n,k, where G_n,k is obtained from the complete graph K_n-k by attaching paths of almost equal lengths to all vertices of K_n-k. We also give a new proof of the analogous result for the spectral radius of the connected graphs with n vertices and k cut vertices (see [A. Berman, X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001) 233-240]). Finally, we discuss the limit point of the maximal signless Laplacian spectral radius.     

The weighted complexity and the determinant functions of graphs

The complexity of a graph can be obtained as a derivative of a variation of the zeta function [S. Northshield, A note on the zeta function of a graph, J. Combin. Theory Ser. B 74 (1998) 408-410] or a partial derivative of its generalized characteristic polynomial evaluated at a point [D. Kim, H.K. Kim, J. Lee, Generalized characteristic polynomials of graph bundles, Linear Algebra Appl. 429 (4) (2008) 688-697]. A similar result for the weighted complexity of weighted graphs was found using a determinant function [H. Mizuno, I. Sato, On the weighted complexity of a regular covering of a graph, J. Combin. Theory Ser. B 89 (2003) 17-26]. In this paper, we consider the determinant function of two variables and discover a condition that the weighted complexity of a weighted graph is a partial derivative of the determinant function evaluated at a point. Consequently, we simply obtain the previous results and disclose a new formula for the complexity from a variation of the Bartholdi zeta function. We also consider a new weighted complexity, for which the weights of spanning trees are taken as the sum of weights of edges in the tree, and find a similar formula for this new weighted complexity. As an application, we compute the weighted complexities of the product of the complete graphs.