On Skew Energy Of Oriented Graphs

Let Ga be an oriented graph of a simple undirected graph G and S(Gσ) be the skew adjacency matrix of Gσ. Then the skew energy εs(Gσ) of the oriented graph Gσ is defined as the sum of the norms of all eigenvalues of S(Ga), which was first put forward by Adiga, Balakrishnan and So in2010and can be viewed as a generalization of the energy of undirected graphs. Whereas the energy of undirected graphs was introduced by Gutman in1977:given a simple undirected graph G, the energy ε(G) of G is defined to be the sum of the absolute values of all eigenvalues of its adjacency matrix A(G).The graph energy has been extensively and deeply studied due to the close relationship between graph energy and theoretical chemistry. However, there are situations when chemists use digraph models rather than undirected graph mod-els. For example, one such situation is when vertices represent distinct chemical species and arcs represent the direction in which a particular reaction takes place between the two corresponding species. So, people hope that this skew energy of oriented graphs can have similar applications as graph energy in chemistry. Now the skew energy has been attracting growing concern.This thesis mainly studies the skew energy of oriented graphs from the fol-lowing aspects:considering the orientation Gσ of a bipartite graph G such that Sps(Gσ)=iSp(G); characterizing all4-regular oriented graphs with optimum skew energy; investigating the orientations of various graph products, and the skew spectra and skew energy of resultant oriented graphs; considering the skew energy in the setting of random oriented graphs.In Chapter1, we first introduce basic notation and terminology in undirected and oriented graphs, and then present the research background of skew energy of oriented graphs. Moreover, we briefly review the development of skew energy, and summarize the main results of this thesis.In Chapter2, we consider the orientations of bipartite graphs such that Sps(Gσ)=iSp(G). Shader and So proved that a graph G is bipartite if and only if there is an orientation Ga of G with Sps(Gσ)=iSp(G), and pointed out that the elementary orientation is such an orientation. Later, Cui and Hou conjectured that such orientation of a bipartite graph G that Sps(Gσ)=iSp(G) is unique under switching-equivalence. This chapter is used to confirm this conjecture and provide an efficient algorithm which transforms the orientation of Ga with Sps(Gσ)=iSp(G) to its elementary orientation by a sequence of switchings.In Chapter3, we focus on optimum skew energy. For any oriented graph Gσ,εs(Ga)÷n(?)â–³, where n andâ–³are the number of vertices and maximum degree of G, respectively. For convenience, the upper bound n(?)â–³is called the optimum skew energy, and the corresponding orientation is called the optimum orientation of G. Adiga, Balakrishnan and So have proved that the graphs with optimum orientation must be regular. This chapter characterizes all4-regular ori-ented graphs with optimum skew energy:first characterizes all possible4-regular graphs with optimum orientations, then illustrates that these regular graphs ex-actly possess optimum orientations and gives the corresponding orientations, and finally proves that the optimum orientations of these regular graphs are unique under switching-equivalence and isomorphism.In Chapter4, we are concerned with the orientations of various graph prod-ucts and skew spectra of the resultant oriented graphs, which includes the Carte-sian product, the Kronecker product, the strong product and the lexicographic product. These graph products, respectively, are discussed in distinct sections: we first give an orientation of each product, and then calculate the skew spec-trum of the resultant oriented graph. Accordingly, we construct some families of oriented graphs with optimum skew energy. Note that the skew adjacency matrix of an oriented graph with optimum skew energy is just a skew weighing matrix, and vice versa. Thus we give a brief introduction of some conjectures and developments on skew weighing matrix.In Chapter5, we investigate the skew energy of oriented graphs in the setting of random graphs. We define two random graph models:the random oriented graph model gσ(n,p) and the random oriented regular graph model gn,dσ.For the random oriented graph model Gσ(n,p), we establish the limiting spectral distribution of skew adjacency matrices of random oriented graphs. Basing on this, we obtain an exact estimate of the skew energy for almost all oriented graphs. For the random oriented regular graph model Gn,dσ, the estimates of skew energy are distinguished into two cases:d fixed and dâ†'∞. And we also formulate exact estimates for the both cases.