Some Extremal Problems On Graph Energy And Skew Energy

For a simple undirected graph G, the energy ε(G) is defined to be the sum of the absolute values of all eigenvalues of its adjacent matrix. Graph energy is closely re-lated to chemistry, there exists a close relationship between eigenvalues of graphs and the molecular orbital energy levels of π-electrons in conjugated hydrocarbons. Ever since the concept of graph energy was proposed by Gutman in1970s, it has been rather widely concerned by theoretical chemists and mathematicians. Particularly since2000, graph energy has been deeply developed and numerous papers were published in vari-ous journals of mathematics and chemistry.Besides graph energy, a few other versions of energy were introduced in the math-ematical literature, an important one is the skew energy. Let G be a digraph with skew-adjacency matrix S(G), the skew energy is defined to be the sum of the norms of its pure imaginary eigenvalues.One of the fundamental problems encountered in the study of graph energy or skew energy is which graph has the maximal or minimal energy within a given class. This thesis is devoted to these problems to determine the extremal graphs or digraphs.In Chapter1, we first give the basic notation and terminology used in this thesis, then introduce the background of the graph energy and skew energy. At last, we list an overview of the main results of this thesis.The second chapter is devoted to giving some preliminary knowledge including the characteristic polynomial, Coulson integral formula, and the main lemmas about the signless matching polynomial.In the next two chapters, we focus on the extremal energy of trees, which is an active research field in graph energy. In2009, Li et al. proved that among trees of order n with two vertices of maximum degree△, the maximal energy tree is either the graph Ta(△,t) or the graph Tb(△,t). Here we denote by Ta(△,t)(or simply Ta) the tree formed from a path Pt on t vertices by attaching△-1P2’s on each end of the path P,, and Tb(△,r)(or simply Tb) the tree formed from P,+2by attaching△-1 P2’s on an end of Pt+2and△-2P2’s on the vertex next to the end, where△≥3and t=n+4-4△≥3. However, they could not determine which one of the trees Ta and Tb is the maximal energy tree. This is because the quasi-order method used before is invalid for comparing their energy.In Chapter3, we create a new method by using the Coulson integral formula, signless matching polynomial, combining some knowledge in analysis and algebra to solve the problem completely. We prove that the maximal energy tree is Tb for△≥7and any t≥3, while the maximal energy tree is Ta for△=3and any t≥3. Moreover, for△=4, the maximal energy tree is Ta for all t≥3except that t=4, for which Tb is the maximal energy tree. For△=5, the maximal energy tree is Tb for all t≥3but44exceptions that t is both odd and3≤t≤89, for which Ta is the maximal energy tree. For△=6, the maximal energy tree is Tb for all t≥3but three exceptions that t=3,5,7, for which Ta is the maximal energy tree. One can see that for most cases of△, Tb is the maximal energy tree,△=5is a turning point, and△=3,4are exceptional cases, which means that for all chemical trees (whose maximum degrees are at most4) with two vertices of maximum degree, Ta has the maximal energy, with only one exception Ta(4,4).In Chapter4, we define the trees with one maximum and one second maximum degree vertex. For d1>d2≥3and t≥3, denote by Tf(d1,d2,t)(or simply Tf) the tree formed from a path Pt on t vertices by attaching d1-1P2’s on one end and d2-1P2’s on the other end of the path Pt, and Tg(d1,d2,t)(or simply Tg) the tree formed from Pt+2by attaching d1-1P2’s on an end of Pt+2and d2-2P2’s on the vertex next to the end. In2010, Yao showed that among trees of order n with two vertices of maximum degree d1and second maximum degree d1(d1> d2), the maximal energy tree is either the graph Tf or the graph Tg. But she could not determine which one of them has the maximal energy.In this chapter, we make use of the difference of two variables skillfully to simplify the calculation, then completely solve this problem. It turns out that things are more complicated here. We prove that the maximal energy tree is Tg if d1≥7,d2≥3or d1=6,d2=3. Moreover, for d1=4and d2=3, the maximal energy tree is the graph Tg if t=4, and the graph Tf otherwise. For other cases, the maximal energy tree is the graph Tf if (ⅰ) d1=5,d2=4,t is odd and3<t<45,(ⅱ) d1-5,d2=3,t is odd and3≤t≤29,(ⅲ) d1=6,d2=5, t=3,5,7,(ⅳ) d1=6,d2=4, t=5; and for all the remaining cases, the maximal energy tree is the graph Tg.In the last chapter, we give some results about the extremal skew energy of di-graphs. Denote by On the class of digraphs with n vertices which have no even cycles, and On,m the digraphs in On with m edges. We first determine the minimal skew en-ergy digraphs in On and On,m(n-1≤m≤3/2(n-1)). Then we get the maximal skew energy digraph in On,m and On,n+1and in the later case we assume n is even.