论文部分内容阅读
极值图论是图论领域中的一个重要分支。在极值图论中一个重要的研究方向是保证图具有某种性质的前提下图的相关参数的变化,包含限制子图的极图问题是这一方向下的一个重要课题,而在这一课题中最有代表性的例子就是Turán类型问题。 早在1940年,著名数学家Turán就给出了一个分析极图的工具,同时也是图论中的一个重要的定理——Turán定理:对于任意的整数r,n,其中r>1,任何一个具有n个顶点的不包含r个顶点的完全图作为子图的简单图的边数至多为Tr-1(n),其中Tr-1(n)是Turán图的边数,n≥r。自此之后,Turán类型问题成为研究的热点问题。许多著名学者对这个问题进行了研究,并取得了许多漂亮的结果。其中,Bollobás等人对于图中含有给定长度的路的数目的极值问题进行了研究,并刻画了相应的极图。受Bollobás等人对于树上给定长度路的数目的研究的启发,Tyomky等人提出了这样一个问题:对于任意一个含有n个顶点的图,它含有距离为k的点对的最大数目是多少呢?为了探究这一问题,他们给出了一些猜想,并用计算机验证了给定确切值的小点图。更进一步,他们对于有限制条件的图得到了如下的结论:当k充分大且n足够大时,一个n阶且不含任三个顶点两两距离值为k的图中含有最大距离为k的顶点对的数目至多为(n-k+1)2/4,等号成立当且仅当此图k-同构于一个“双扫帚”。 实际上,距离相等的点对数目的极值问题很早就引起了人们的关注。当k=3时,此问题就成为化学图论中的一个著名的指数——Wiener极化指数,它是由著名化学家H.Wiener在1947年提出的。Wiener极化指数主要是在理论化学中用来反映分子的物理化学性质,药学性质等各种性质。具体来说,它可以被用在一些无圈和单圈的碳氢化合物中来量化其结构性质。很多研究人员都对此指标进行了一系列的研究并取得了一些好的结果。其中,树和单圈图中具有最大、最小的Wiener极化指数的极图已被完全刻画。 对于一般的k值,此问题的研究是困难的。本论文主要是针对给定k值为2和3的点对数目问题进行研究并得到了一些相应的结果。全文共分为五章。在第一章中,我们介绍了本文所涉及到的基本概念,研究背景以及主要结果。 在第二章中,我们主要对Tyomkyn和Uzzell的一个猜测进行了研究。猜测如下:一个具有n(≥5)个顶点且不含有三个顶点两两距离为2的简单图的距离为2的点对数目不超过(n-1)2/4+1。对于顶点数小于11的情形,他们用计算机验证了其正确性。而在这一章,我们通过对图结构的分析得到了一个更一般的结论:对于一个n(≥5)阶且不含有三个顶点两两距离为2的简单图,如果它含有一个顶点,其邻域至多被两个团覆盖,那么该图的距离为2的点对的数目至多为(n-1)2/4+1,并且我们完全刻画了其极图。 在第三章中,我们主要研究了图积下的Wiener极化指数。图积是图论中构造新图的重要方法,在网络构造和设计中有着重要的应用。在这一章,我们研究Wiener极化指数在四种图积(卡氏积、强积、直积、字典积)下的变化,并给出了图积下Wiener极化指数的关系式。 在第四章中,我们主要研究了双圈图的Wiener极化指数。杜等人给出了对于树的Wiener极化指数的一个线性算法并刻画了具有最大Wiener极化指数的极图。随后一些研究者给出了计算树、单圈图的Wiener极化指数的公式,并且刻画了给定直径、最大度条件下的单圈图中的最大、最小的Wiener极性指标的极图。在这一章中,我们给出了双圈图的Wiener极化指数的计算公式,并且刻画了具有最大、最小Wiener极化指数相应的极图。 在第五章中,我们总结了这类Turán类型问题,列出了几个已知的猜想和问题,并给出了几个有待继续探索研究的方向。