论文部分内容阅读
用n和m分别表示一个连通简单图G的顶点个数和边数,称c(G)=m-n+1为图G的基本圈数。我们用图的基本圈的个数来定义无圈、单圈,双圈乃至k-圈图。当c(G)=0时,称G为无圈图或树。当c(G)=1时,称G为单圈图。类似地,当c(V)=k时,称G为k-圈图。
对给定简单图G,用A(G)表示它的邻接矩阵。图G的能量定义为它的邻接矩阵A(G)的所有特征值的绝对值之和。这一定义的重要化学背景是图的特征值与共轭碳氢化合物中7-电子的分子轨道能量级有着紧密的对应。事实上,这一定义来自于对全开-电子能量的Hiickel分子轨道近似。1940年,Coulson等人在研究化学分子能量时对这一事实就有了一些认识和结论。1978年,Gutman在之前工作的基础上,正式提出了图的能量的(数学)概念,这一概念不仅适用于分子图,也适用于一般图。
1977年,Gutman首先定义了二部图的拟序关系。利用图的拟序关系可以有效地解决关于图极值能量的很多问题,并且一直以来这都是解决此类问题的主要方法。然而,随着研究的不断深入,逐渐出现了一大批用拟序关系不能解决的能量的极值问题,我们称之为拟序不可比问题。长期以来,人们一直试图去攻克这些拟序不可比问题。最近,我们找到了一种处理这类问题的有效方法。运用了分析、代数和组合方法,同时主要依据能量的Coulson积分公式,我们成功地解决了这一系列长期未解决的极值能量问题。
1999年,Zhang和Li在讨论无圈共轭分子图的极小能量时,发现在具有完美匹配的树中,具有第三极小能量的树是两个拟序不可比的图之一.在2.1节,我们在前人工作的基础上,完全解决了这一问题,并确定了第三到第六极小能量图。
2008年,Gutmaa等人猜想具有第四极大能量的树是图R(2,6,n-9),它由从唯一的一个三度点出发的三条内部不交的悬挂路构成,这三条路的长度分别为2,6和n-9。2009年,Shao和Li等人用拟序关系和图运算的方法得到第四极大能量树是R(2,6,n-9)或者瓦(2,212,2),后者表示在n-8个顶点的路的每个端点上分别粘接两条长为2的悬挂路所得到的图。然而,这两个图也无法用拟序来比较。在2.2节,我们研究了此问题并确定了第四极大能量树。
2007年,Hua和Wang研究了有固定悬挂点数目的单圈图,发现其中具有极小能量的图在某些情况下同样需要在两个拟序不可比图中选择。在3.1节,我们完全确定了此情况下具有极小能量的图。
1999年,Caporossi,Cvetkovic,Gutman和Hansen等人猜想,对n个顶点的单圈图,当n<7或者n=9,10,11,13,15时,圈Gn具有极大能量;对其余的n,图具有极大能量,其中P6n是由一条n-5个顶点的路的一个端点粘接一个圈所得到的。对于单圈二部图的情况,2002年,Hou,Gutman和Woo等人利用拟序关系的方法证明具有极大能量的n阶单圈二部图是G或者,但他们不能确定到底是哪个图达到极大能量,因为这两个图是拟序不可比的。在3.2节,我们完全确定了单圈二部图中的极大能量图。更进一步,在此基础上,我们在3.3节彻底解决了这个猜想。