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 bicyclic graphs with maximal energy

Let λ₁,λ₂,…,λ_n be the eigenvalues of a graph G of order n. The energy of G is defined as E(G)=|λ₁|+|λ₂|+?+|λ_n|. Let be the graph obtained from two copies of C₆ joined by a path P_n-10, B_n be the class of all bipartite bicyclic graphs that are not the graph obtained from two cycles C_a and C_b (a,b?10 and a≡b≡2 (mod 4)) joined by an edge. In this paper, we show that is the graph with maximal energy in B_n, which gives a partial solution to Gutman’s conjecture in Gutman and Vidovi? (2001) [I. Gutman, D. Vidovi?, Quest for molecular graphs with maximal energy: a computer experiment, J. Chem. Inf. Sci. 41 (2001) 1002-1005].     

Classes of graphs with minimum skew rank 4

The minimum skew rank of a simple graph G   is the smallest possible rank among all real skew-symmetric matrices whose (i,j)$(i,j)$-entry is nonzero if and only if the edge joining i and j is in G. It is known that a graph has minimum skew rank 2 if and only if it consists of a complete multipartite graph and some isolated vertices. Some necessary conditions for a graph to have minimum skew rank 4 are established, and several families of graphs with minimum skew rank 4 are given. Linear algebraic techniques are developed to show that complements of trees and certain outerplanar graphs have minimum skew rank 4.     

On oriented graphs whose skew spectral radii do not exceed 2

Let S(G^σ)$S(G^{\sigma })$ be the skew adjacency matrix of the oriented graph G^σ$G^{\sigma }$ of order n   and _λ1,_λ2,…,_λn${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ be all eigenvalues of S(G^σ)$S(G^{\sigma })$. The skew spectral radius _ρs(G^σ)${\rho }_s(G^{\sigma })$ of G^σ$G^{\sigma }$ is defined as max{|_λ1|,|_λ2|,…,|_λn|}$\max \{|{\lambda }_1|,|{\lambda }_2|,\dots ,|{\lambda }_n|\}$. In this paper, we investigate oriented graphs whose skew spectral radii do not exceed 2.     

3-Regular digraphs with optimum skew energy

The skew energy of a digraph D is defined as the sum of the singular values of its skew adjacency matrix $S(D)$. In this paper, we first interpret the entries of the power of the skew adjacency matrix of a digraph in terms of the number of its walks and then focus on the question posed by Adiga et al. [C. Adiga, R. Balakrishnan, Wasin So, The skew energy of a graph, Linear Algebra Appl. 432 (2010) 1825–1835] of determining all $3$-regular connected digraphs with optimum skew energy.     

The skew energy of a digraph

We are interested in the energy of the skew-adjacency matrix of a directed graph D, which is simply called the skew energy of D in this paper. Properties of the skew energy of D are studied. In particular, a sharp upper bound for the skew energy of D is derived in terms of the order of D and the maximum degree of its underlying undirected graph. An infinite family of digraphs attaining the maximum skew energy is constructed. Moreover, the skew energy of a directed tree is independent of its orientation, and interestingly it is equal to the energy of the underlying undirected tree. Skew energies of directed cycles under different orientations are also computed. Some open problems are presented.     

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 .     

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.     

The least eigenvalue of graphs with given connectivity

Let G be a simple graph and A(G) be the adjacency matrix of G. The eigenvalues of G are those of A(G). In this paper, we characterize the graphs with the minimal least eigenvalue among all graphs of fixed order with given vertex connectivity or edge connectivity.     

On tricyclic graphs of a given diameter with minimal energy

The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. Let G(n,d) be the class of tricyclic graphs G on n vertices with diameter d and containing no vertex disjoint odd cycles C_p,C_q of lengths p and q with p+q≡2(mod4). In this paper, we characterize the graphs with minimal energy in G(n,d).     

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.     

Integral complete 4-partite graphs

A graph G is called integral if all the roots of the characteristic polynomial P(G;x) are integers. In the paper the first known integral complete 4-partite graph K_p1,p2,p3,p4, where p₁<p₂<p₃<p₄, is constructed.     

Improved bounds for the Laplacian energy of Bethe trees

For k, d?2, a Bethe tree is a rooted tree with k levels which the root vertex has degree d, the vertices from level 2 to k-1 have degree d+1 and the vertices at the level k are pendent vertices. So et al, using a theorem by Ky Fan have obtained both upper and lower bounds for the Laplacian energy of bipartite graphs. We shall employ the above mentioned theorem to obtain new and improved bounds for the Laplacian energy in the case of Bethe trees.     

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.     

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.     

A sharp upper bound on the signless Laplacian spectral radius of graphs

Let G be a simple connected graph of order n   with degree sequence _d1,_d2,…,_dn$d_1,d_2,\dots ,d_n$ in non-increasing order. The signless Laplacian spectral radius ρ(Q(G))$\rho (Q(G))$ of G   is the largest eigenvalue of its signless Laplacian matrix Q(G)$Q(G)$. In this paper, we give a sharp upper bound on the signless Laplacian spectral radius ρ(Q(G))$\rho (Q(G))$ in terms of _di$d_i$, which improves and generalizes some known results.     

A characterization of graphs with rank 4

The rank of a graph G is defined to be the rank of its adjacency matrix. In this paper, we consider the following problem: What is the structure of a connected graph with rank 4? This question has not yet been fully answered in the literature, and only some partial results are known. In this paper we resolve this question by completely characterizing graphs G whose adjacency matrix has rank 4.     

The asymptotic numbers of regular tournaments,Eulerian digraphs and Eulerian oriented graphs

LetRT(n), ED(n) andEOG(n) be the number of labelled regular tournaments, labelled loop-free simple Eulerian digraphs, and labelled Eulerian oriented simple graphs, respectively, onn vertices. Then, asn,, for any>0. The last two families of graphs are also enumerated by their numbers of edges. The proofs use the saddle point method applied to appropriaten-dimensional integrals.     

Applications of a theorem by Ky Fan in the theory of graph energy

The energy of a graph G is equal to the sum of the absolute values of the eigenvalues of G, which in turn is equal to the sum of the singular values of the adjacency matrix of G. Let X, Y, and Z be matrices, such that X+Y=Z. The Ky Fan theorem establishes an inequality between the sum of the singular values of Z and the sum of the sum of the singular values of X and Y. This theorem is applied in the theory of graph energy, resulting in several new inequalities, as well as new proofs of some earlier known inequalities.