【作者】 李静；

【导师】 李学良；

【作者基本信息】 南开大学 ， 应用数学， 2013， 博士

【摘要】 对一个简单无向图G,它的能量(G)定义为对应邻接矩阵的所有特征值的绝对值之和。图能量和化学有着非常密切的关系,特别是图的特征值和共轭碳氢化合物中π-电子的分子轨道能量之间存在着紧密对应。自1977年Gutman提出图能量的概念后,就引起了很多理论化学家和数学家的关注。尤其是2000年以后,图能量更是得到了长足发展,大量论文发表在各类数学化学期刊上。除了图能量,一些其他类型的能量也在数学上被提出,其中非常重要的一个就是有向图的斜能量,它定义为有向图斜邻接矩阵的特征值的模之和。在图能量和斜能量的研究中,我们遇到的一个基本问题,就是在给定的图类中确定哪些图具有极大或极小能量。本文完全解决了关于给定最大顶点度的树的两个极大能量问题,对有向图的极值问题,也给出了非常好的结果。第一章是引言,我们首先给出了文中涉及的基本概念和相关知识,然后介绍了图能量和斜能量的相关背景,最后列出了这篇论文的主要结果。第二章给出了本文涉及到的一些预备知识,包括：特征多项式,Coulson积分公式以及关于无符号匹配多项式的主要引理。在接下来的两章中,我们研究一类非常重要的图,树。2009年,李学良等人证明了在所有n个顶点并且其中两个顶点具有最大度△的树中,瓦(△,t)或者死(△,t)具有极大能量。其中死(△,t)(简写为死)表示在路B的两个端点处各连接△一1个p2后得到的树,死(△,t)(简写为死)表示在路另+2的一个端点处连接△一1个恳,在这个端点的邻点处连接△一2个P2后得到的树,此处△≥3,t=n+4－4△≥3。但是他们不能确定到底是死还是乃更大一些,因为之前常用的拟序比较方法在这里失效了。在第三章中,我们创造性地将无符号匹配多项式引入图能量的Coulson积分公式,结合分析和代数方法,成功地解决了这一问题。我们证明对所有△≥7,t≥3的情况,极大能量树是死,对△=3,t≥3的情况,极大能量树是死。此外,如果△=4,除了t=4时极大能量树为死,其他情况下都为乃。对△=5,在t为3到89之间的奇数时,极大能量树为瓦,其他情况下为死。△=6时,只有t=3,5,7这三种情况下极大能量树为瓦,其余情况均为死。很明显可以看出,对大部分情况,Tb我们要找的极大能量树,△=5是一个转折点,△=3,4是特殊情况。这也就意味着,对所有的化学树(最大度至多为4的树),除了Ta4,4)之外,Ta是极大能量树。在第四章中,我们类似地定义具有一个最大度顶点一个次最大度顶点的树。令Tf(d1,d2,t)(简写Pt)表示在路Pt的一个端点处连接d1-1个p2,另一个端点处连接d2一1个恐后得到的树,%(d1,d2,t)(简写为T8)表示在路Pt+2的一个端点处连接d1-1个P2,在这个端点的邻点处连接d2-1个最后得到的树,其中d1>d2≥3,t≥3。姚祥妹在2010年证明了对所有n个顶点,其中两个顶点分别具有最大度d1和次最大度d2的树,Tf或者T8具有极大能量。但是确定到底是Tf还是T8更大一些仍是一个难题。上述问题涉及更多变量,因此其证明更加困难。我们巧妙地利用两个变量的差简化计算,配合使用分析和代数方法,完全解决了这个问题。我们证明了对d1≥7,d2≥3或者d1=6,d2=3的情况,T8是极大能量树。如果d1=4且d2=3,当t=4时T8具有极大能量,其余情况Tf具有极大能量。对于剩下的情况,当(i)d1=5,d2=4,t是3到45之间的奇数；(ii)d1=5,d2=3,t是3到29之间的奇数；(iii)dl=6,d2=5,t=3,5,7；(iv)dl=6,比=4,t=5的时候,极大能量树为Tf,其余情况为T8。最后一章给出了关于有向图的斜能量的一些研究结果。令方。表示具有n个顶点,不包含偶圈的有向图,方n,m表示方n中边数为m的图类,我们确定了方n和方n,m研一1≤m≤主@一1))这两类图中的极小斜能量有向图,并且得到了方M以及方M+1(n为偶数)中的极大斜能量有向图。更多还原

【Abstract】 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.更多还原