The Energy And The Laplacian Energy Of Random Graphs

As well known, graph theory has a broad range of application to many fields, such as physics and chemistry, and our work is concerned with an algebraic invariant of graphs which can enables us to calculate the total energy of 7r-electrons in conjugated hydrocarbons.Let G be an undirected simple graph of order n. A(G) stands for the adja-cency matrix of G, and the eigenvaluesλ1,...,λn of A(G) are called the eigen-values of G. In 1930s, Erich Huckel suggested an approach to find approximate solutions of the Schrodinger equation for conjugated hydrocarbons, which can be used to estimate the molecular orbital energy levels ofπ-electrons in conjugated hydrocarbons, and to calculate the total energy ofπ-electrons in the hydrocar-bons. In 1970s, Gutman found that the nontrivial part to calculate the energy is equal to∑i=1n|λ'i| whereλ'1,...,λ'n are the eigenvalues of a molecular graph G' corresponding to some carbon-atom skeleton of the underlying conjugated molecule, and then he generalized this concept to all simple graphs and defined the energy of G to beε(G)=∑i=1n|λi| whereλ1,...,λn are the eigenvalues of the graph G.Evidently, one can immediately calculate the energy of a graph by comput-ing the eigenvalues of the graph. It is rather hard, however, to compute the eigenvalues for a large matrix, even for a large symmetric (0,1)-matrix like A(G). So many researchers established lots of lower and upper bounds to estimate the invariant for some classes of graphs. However, those bounds have a common flaw that there are only a few classes of graphs attaining the equalities of those bounds. Thus one can hardly see the major behavior of the invariantε(G) for most graphs with respect to other graph parameters (|V(G)|, for instance). It is surprised that one can employ the probabilistic and algebraic approaches to obtain an exact estimate of energy for almost all graphs. In the second chapter, we first explore the energy for random graphs Gn(p)∈(?)(p), where (?)n(p) denotes the Erdos-Renyi random graph model, and show that almost every graph Gn(p) enjoys the followingThen we investigate the energy for random multipartite graphs which can be viewed as a generalization to the Erdos-Renyi model. We use Kn;v1,...vm to de-note the complete m-partite graph with vertex set [n]:={1,...,n} whose parts V1,...,Vm(m=m(n)≥2) are such that |Vi|= nvi = nvi(n), i= 1,..., m. Let (?)n;v1...vm(p) be the set of random m-partite graphs with vertex set [n] in which the edges are chosen independently with probability p from the set of edges of Kn;v1,...,vm.Denote by (?)n,m(p) and (?)'n,m(p) the sets of random m-partite graphs satisfying, respectively, the following conditions: and In Section 2.2, we show that almost every random graph Gn,m(p)∈(?)n,m(p) and G'n,m(p)∈(?)'n,m(p) enjoys the following: and Finally, we consider the energy for another sort of random multipartite graphs Gn;v1...vm(p) which satisfies the following requirement and there exist vi and Vj with and show that almost every random graph Gn;v1...vm (p) enjoys the inequality below where r is an integer such that|V1|,....,|Vr| are of order O(n) and|Vr+1|,...,|Vm| of order o(n).In spectral graph theory, the matrix L(G)=D(G)-A(G) is called Laplacian matrix of G, where D(G) is a diagonal matrix in which dii equals the degree dG(vi) of the vertex vi, i=1,...,n. Gutman et al. introduced a new matrix L(G) for a simple graph G, i.e., i=i i=i j>i where In is the unit matrix of order n, and defined the Laplacian energyεL(G) of G, i.e., whereζ1,...,ζn are the eigenvalues of L(G). In a recent paper, Gutman et al. proposed a conjecture that for any graph G,ε(G)≤εL(G). Unfortunately, the conjecture turns out to be incorrect. In fact, Liu et al. and Stevanovic et al. constructed two classes of graphs violating the assertion. How-ever, So et al. proved that the conjecture is true for bipartite graphs. In Chapter 3, we establish an estimate to the Laplacian energy for almost all graphs and show that almost every random graph Gn(p) satisfies the following bound By the assertion above, one can readily show that the conjecture above is true for almost all graphs.Recently, several other energy-like quantities, which relate to eigenvalues of some matrices, such as signless Laplacian energy, Laplacian-energy like invariant, incidence energy, distance energy and Von Neumann entropy, have been presented and studied in mathematical, mathematica-chemical and mathematica-physical literatures. In the last chapter, we investigate those quantities by the approaches we employ to characterize the energy and Laplacian energy, and formulate some estimates for those quantities.