关于(修正)Szeged指标的若干猜想的证明

来源 :南开大学 | 被引量 : 0次 | 上传用户:yeluanwu
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
所谓的拓扑指标指的是从分子图到实数集的以某种确定方式的一个映射。拓扑指标是图的不变量,只与图的大小和形状有关。在理论化学中,拓扑指标可以反应分子的物理化学性质,药学性质,生物学性质以及化合物的各种性质。因此,拓扑指标在化学,药理学,毒药学和生物学中有着广泛的应用。  众所周知,在化学中,最早被研究的拓扑指标是Wiener指标,它是由著名化学家H.Wiener在1947年研究烷烃的沸点时提出来的。一个图G的Wiener指标W(G)是指图G中所有顶点对的距离之和,即:W(G)=∑{u,v}(∈)V(G) dG(u,v).  自那之后,Wiener指标被用来解释分子的各种物理化学性质以及与分子结构相关联的生物活性,因此,Wiener指标得到了许多数学家和化学家的注意和研究。  1994年著名化学家I.Gutman提出了Szeged指标Sz(G):Sz(G)=∑e=uv∈E(G) nu(e)nv(e),  其中nu(e)是到顶点u的距离小于到顶点v的距离的所有顶点的个数,nv(e)是到顶点v的距离小于到顶点u的距离的所有顶点的个数。当G是树时,Sz(G)=W(G)。实际上,Szeged指标是Wiener指标的推广。很显然,这里并没有考虑到顶点u的距离等于到顶点v的距离的那些顶点,注意到这点之后,M.Randi(c)提出了修正Szeged指标。  一个图G的修正Szeged指标Sz*(G)定义为:Sz*(G)=Σe=uv∈E(G)(nu(e)+no(e)/2)(nv(e)+no(e)/2),  其中no(e)是到顶点u和顶点v的距离相等的所有顶点的个数。  2011年,周等人对于顶点数为n≥5的单圈图确定了其修正Szeged指标的最大值和最小值,同时,对于顶点数为n(≥5)和圈长为r(3≤r≤n)的单圈图也确定了其修正Szeged指标的最大值和最小值。2010年,Hansen等人  猜想,对于连通的双圈图,具有极大的修正Szeged指标的图应该是Bn,其中Bn是由n-1个顶点的圈Cn-1通过复制一个顶点得到的。在本文的第二章,我们完全解决了这个猜想,同时还确定了第二大修正Szeged指标的连通双圈图。2010年,Aouchiche和Hansen给出了关于一般连通图G的修正Szeged指标的一个上界,即,Sz*(G)≤n2m/4,其中n和m分别为图G的顶点数和边数。对于双圈图,我们得到的上界结果要优于n2m/4。  本文的第三章,我们继续对三圈图进行研究。对于连通的三圈图,我们给出其修正Szeged指标的一个上界,同时我们刻画出所有达到此上界的极值图。对于三圈图,我们得到的上界结果也要优于一般图的界n2m/4。  2010年,Hansen等人提出四个关于Szeged指标Sz(G)和Wiener指标W(G)以及修正Szeged指标Sz*(G)和Wiener指标W(G)之间差值的猜想。首先,对于二部连通图G,满足阶数n≥4以及边数m≥n,他们猜想Sz(G)-W(G)≥4n-8,并且,当图是由4个顶点的圈和n-3个顶点的树通过粘合一个顶点得到时,可以达到此下界。在4.2节,我们完全解决了这个猜想,同时给出了等式成立的充分必要条件。当图G是二部图时,很显然有no(e)=0,那么,Sz*(G)=Sz(G)。因此,对于一个图的修正Szeged指标Sz*(G)和Wiener指标W(G)之间的差值,我们可以得到同样的结果。遗憾的是,这个猜想的证明方法并不适用于非二部图。  对于非二部图G,满足阶数n≥5并且围长g≥5,他们猜想Sz(G)-W(G)≥2n-5,并且,当图是由5个顶点的圈和n-4个顶点的树通过粘合一个顶点得到时,可以达到此下界。在4.3节,我们用一个新方法证明了这个猜想,并且完全刻画了达到此下界的所有极值图。应该指出的是,除了猜想中所叙述的那个图之外,我们还找到另外一类图也可以达到上述猜想的下界,这个图是由5个顶点的圈C5和两棵树T1,T2构成,并且满足T1,T2的两个根节点为圈G5上的两个相邻顶点。同时可以看到,这个新方法同样适用于二部图的情况,因此对于二部图,我们给出了另外一种证明。对于阶数为n≥4的非二部连通图,他们还猜想Sz*(G)-W(G)≥(n2+4n-6)/4,并且,当图是由3个顶点的圈和n-2个顶点的树通过粘合一个顶点得到时,可以达到此下界。在4.3节,我们同样完全地解决了这个猜想。
其他文献
滤波反投影算法的关键是滤波函数,该文提出一种新型滤波函数,其主要部分为泛函分析中的磨光算子.作为滤波函数,它具有许多优异的性质.分析其时频特性并给出用于CT重建的误差
传统意义上投资环境的建设与研究,多是站在政府管理者的立场,从静态的角度进行,因而缺乏系统观与动态观,忽视了投资行为与环境要素的互动连锁性.该文认为,厂商作为一个"经济
分类或刻画具有各种传递性质(例如点传递、边传递、弧传递等)的图是代数图论中一个非常重要且活跃的研究课题。在本文中我们主要研究边传递图,特别是半对称图即边传递但不是点传
全文共分五节:第一节主要研究推广扭曲smash积,第二节主要研究了推广扭曲smash积的对偶,第三节主要研究了Biproduct的一种推广,第四节主要研究了双模上Biproduct的推广,作为