The Estrada index of trees

The Estrada index of a graph G is defined as , where λ₁,λ₂,…,λ_n are the eigenvalues of its adjacency matrix. We determine the unique tree with maximum Estrada index among the set of trees with given number of pendant vertices. As applications, we determine trees with maximum Estrada index among the set of trees with given matching number, independence number, and domination number, respectively. Finally, we give a proof of a conjecture in [J. Li, X. Li, L. Wang, The minimal Estrada index of trees with two maximum degree vertices, MATCH Commun. Math. Comput. Chem. 64 (2010) 799-810] on trees with minimum Estrada index among the set of trees with two adjacent vertices of maximum degree.     

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.     

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.     

Note on the energy of regular graphs

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all the eigenvalues of its adjacency matrix A(G). Let n,m, respectively, be the number of vertices and edges of G. One well-known inequality is that , where λ₁ is the spectral radius. If G is k-regular, we have . Denote . Balakrishnan [R. Balakrishnan, The energy of a graph, Linear Algebra Appl. 387 (2004) 287-295] proved that for each ?>0, there exist infinitely many n for each of which there exists a k-regular graph G of order n with k<n-1 and , and proposed an open problem that, given a positive integer n?3, and ?>0, does there exist a k-regular graph G of order n such that . In this paper, we show that for each ?>0, there exist infinitely many such n that . Moreover, we construct another class of simpler graphs which also supports the first assertion that .     

On the spectral radii and the signless Laplacian spectral radii of c-cyclic graphs with fixed maximum degree

If G is a connected undirected simple graph on n vertices and n+c-1 edges, then G is called a c-cyclic graph. Specially, G is called a tricyclic graph if c=3. Let Δ(G) be the maximum degree of G. In this paper, we determine the structural characterizations of the c-cyclic graphs, which have the maximum spectral radii (resp. signless Laplacian spectral radii) in the class of c-cyclic graphs on n vertices with fixed maximum degree . Moreover, we prove that the spectral radius of a tricyclic graph G strictly increases with its maximum degree when , and identify the first six largest spectral radii and the corresponding graphs in the class of tricyclic graphs on n vertices.     

Maximal reflexive cacti with four cycles: The approach via Smith graphs

Cacti, or treelike graphs, are graphs whose all cycles are mutually edge-disjoint. Graphs with the property are called reflexive graphs, where λ₂ is the second largest eigenvalue of the corresponding (0, 1)-adjacency matrix. The property is a hereditary one, i.e. all induced subgraphs of a reflexive graph are also reflexive. This is why we represent reflexive graphs through the maximal graphs within a given class (such as connected cacti with a fixed number of cycles). In previous work we have determined all maximal reflexive cacti with four cycles whose cycles do not form a bundle and pointed out the role of so-called pouring of Smith graphs in their construction. In this paper, besides pouring, we show several other patterns of the appearance of Smith trees in those constructions. These include splitting of a Smith tree, adding an edge to a Smith tree and then splitting of the resulting graph, identifying two vertices of a Smith tree and then splitting the resulting graph. Our results show that the presence of Smith trees is evident in all such maximal reflexive cacti with four cycles and that in most of them Smith graphs appear in the described way.     

On the skew energy of orientations of hypercubes

Let D be a digraph of order n and λ₁,λ₂,…,λ_n denote all the eigenvalues of the skew-adjacency matrix of D. The skew energy E_S(D) of D is defined as . In this paper, it is proved that for any positive integer k≥3, there exists a k-regular graph of order n having an orientation D with . This work positively answers a problem proposed by Adiga et al. [C. Adiga, R. Balakrishnan, Wasin So, The skew energy of a digraph, Linear Algebra Appl. 432 (2010) 1825-1835]. In addition, a digraph is also constructed such that its skew energy is the same as the energy of its underlying graph.     

On the Laplacian spectral radii of trees

Let Δ(T) and μ(T) denote the maximum degree and the Laplacian spectral radius of a tree T, respectively. Let T_n be the set of trees on n vertices, and . In this paper, we determine the two trees which take the first two largest values of μ(T) of the trees T in when . And among the trees in , the tree which alone minimizes the Laplacian spectral radius is characterized. We also prove that for two trees T₁ and T₂ in , if Δ(T₁)>Δ(T₂) and , then μ(T₁)>μ(T₂). As an application of these results, we give a general approach about extending the known ordering of trees in T_n by their Laplacian spectral radii.     

Spectral radius and Hamiltonicity of graphs

Let G be a graph of order n and μ(G) be the largest eigenvalue of its adjacency matrix. Let be the complement of G.Write K_n-1+v for the complete graph on n-1 vertices together with an isolated vertex, and K_n-1+e for the complete graph on n-1 vertices with a pendent edge.We show that:If μ(G)?n-2, then G contains a Hamiltonian path unless G=K_n-1+v; if strict inequality holds, then G contains a Hamiltonian cycle unless G=K_n-1+e.If , then G contains a Hamiltonian path unless G=K_n-1+v.If , then G contains a Hamiltonian cycle unless G=K_n-1+e.     

r-Strong edge colorings of graphs

Let G be a graph and for any natural number r, denotes the minimum number of colors required for a proper edge coloring of G in which no two vertices with distance at most r are incident to edges colored with the same set of colors. In [Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626] it has been proved that for any tree T with at least three vertices, . Here we generalize this result and show that . Moreover, we show that if for any two vertices u and v with maximum degree d(u,v)?3, then . Also for any tree T with Δ(T)?3 we prove that . Finally, it is shown that for any graph G with no isolated edges, .     

On conjugate adjacency matrices of a graph

Let G be a simple graph of order n. Let and , where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. We say that A^c=[c_ij] is the conjugate adjacency matrix of the graph G if c_ij=c for any two adjacent vertices i and j, for any two nonadjacent vertices i and j, and c_ij=0 if i=j. Let P_G(λ)=|λI-A| and denote the characteristic polynomial and the conjugate characteristic polynomial of G, respectively. In this work we show that if then , where denotes the complement of G. In particular, we prove that if and only if P_G(λ)=P_H(λ) and . Further, let P^c(G) be the collection of conjugate characteristic polynomials of vertex-deleted subgraphs G_i=G?i(i=1,2,…,n). If P^c(G)=P^c(H) we prove that , provided that the order of G is greater than 2.     

Extremal energies of trees with a given domination number

The energy of a graph is defined as the sum of the absolute values of the eigenvalues of its adjacency matrix. Let T(n,γ) be the set of trees of order n and with domination number γ. In this paper, we characterize the tree from T(n,γ) with the minimal energy, and determine the tree from T(n,γ) where n=kγ with maximal energy for .     

The ordering of trees and connected graphs by algebraic connectivity

In this paper, we first determine that the first four trees of order n?9 with the smallest algebraic connectivity are P_n,Q_n,W_n and Z_n with α(P_n)<α(Q_n)<α(W_n)<α(Z_n)<α(T), where T is any tree of order n other than P_n, Q_n, W_n, and Z_n. Then we consider the effect on the Laplacian eigenvalues of connected graphs by suitably adding edges. By using these results and methods, we finally determine that the first six connected graphs of order n?9 with the smallest algebraic connectivity are and , with , where G is any connected graph of order n other than P_n, Q_n, , W_n, and .     

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.     

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.     

Carleson measure problems for parabolic Bergman spaces and homogeneous Sobolev spaces

Let be the space of solutions to the parabolic equation having finite norm. We characterize nonnegative Radon measures μ on having the property , 1≤p≤q<∞, whenever . Meanwhile, denoting by v(t,x) the solution of the above equation with Cauchy data v₀(x), we characterize nonnegative Radon measures μ on satisfying , β∈(0,n), p∈[1,n/β], q∈(0,∞). Moreover, we obtain the decay of v(t,x), an isocapacitary inequality and a trace inequality.     

The Laplacian spectral radius of some bipartite graphs

In this paper, we study the largest Laplacian spectral radius of the bipartite graphs with n vertices and k cut edges and the bicyclic bipartite graphs, respectively. Identifying the center of a star K_1,k and one vertex of degree n of K_m,n, we denote by the resulting graph. We show that the graph (1?k?n-4) is the unique graph with the largest Laplacian spectral radius among the bipartite graphs with n vertices and k cut edges, and (n?7) is the unique graph with the largest Laplacian spectral radius among all the bicyclic bipartite graphs.     

Bounds and conjectures for the signless Laplacian index of graphs

Using the AutoGraphiX system, we obtain conjectures of the form l(n)?q₁⊕i(G)?u(n) where q₁ denotes the signless Laplacian index of graph is one the four operations is another invariant chosen among minimum, average and maximum degree, average distance, diameter, radius, girth, proximity, remoteness, vertex, edge and algebraic connectivities, independence number, domination number, clique number, chromatic number and matching number, Randi? index, l(n) and u(n) are best possible lower and upper bounds function of the order n of G. Algebraic conjectures are obtained in 120 cases out of 152 and structural conjectures in 12 of the remaining cases. These conjectures are known, immediate or proved in this paper, except for 17 of them, which remain open.     

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.     

A generalization of a conjecture due to Erd?s, Jacobson and Lehel

An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m+1 vertices, denoted by , is an r-graph on m+1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is r-graphic if it is realizable by an r-graph on n vertices. Let be the smallest even integer such that each n-term r-graphic sequence with term sum of at least is realizable by an r-graph containing as a subgraph. In this paper, we determine the value of for sufficiently large n, which generalizes a conjecture due to Erd?s, Jacobson and Lehel.