距離為給定值的點對數(shù)目的若干問題.pdf

1、極值圖論是圖論領(lǐng)域中的一個重要分支。在極值圖論中一個重要的研究方向是保證圖具有某種性質(zhì)的前提下圖的相關(guān)參數(shù)的變化，包含限制子圖的極圖問題是這一方向下的一個重要課題，而在這一課題中最有代表性的例子就是Turán類型問題。
　　早在1940年，著名數(shù)學(xué)家Turán就給出了一個分析極圖的工具，同時也是圖論中的一個重要的定理——Turán定理：對于任意的整數(shù)r,n，其中r>1，任何一個具有n個頂點的不包含r個頂點的完全圖作為子圖的簡單圖的

2、邊數(shù)至多為Tr-1(n)，其中Tr-1(n)是Turán圖的邊數(shù)，n≥r。自此之后，Turán類型問題成為研究的熱點問題。許多著名學(xué)者對這個問題進行了研究，并取得了許多漂亮的結(jié)果。其中，Bollobás等人對于圖中含有給定長度的路的數(shù)目的極值問題進行了研究，并刻畫了相應(yīng)的極圖。受Bollobás等人對于樹上給定長度路的數(shù)目的研究的啟發(fā)，Tyomky等人提出了這樣一個問題：對于任意一個含有n個頂點的圖，它含有距離為k的點對的最大數(shù)目是多少

3、呢？為了探究這一問題，他們給出了一些猜想，并用計算機驗證了給定確切值的小點圖。更進一步，他們對于有限制條件的圖得到了如下的結(jié)論：當k充分大且n足夠大時，一個n階且不含任三個頂點兩兩距離值為k的圖中含有最大距離為k的頂點對的數(shù)目至多為(n-k+1)2/4，等號成立當且僅當此圖k-同構(gòu)于一個“雙掃帚”。
　　實際上，距離相等的點對數(shù)目的極值問題很早就引起了人們的關(guān)注。當k=3時，此問題就成為化學(xué)圖論中的一個著名的指數(shù)——Wiener極

4、化指數(shù)，它是由著名化學(xué)家H.Wiener在1947年提出的。Wiener極化指數(shù)主要是在理論化學(xué)中用來反映分子的物理化學(xué)性質(zhì)，藥學(xué)性質(zhì)等各種性質(zhì)。具體來說，它可以被用在一些無圈和單圈的碳氫化合物中來量化其結(jié)構(gòu)性質(zhì)。很多研究人員都對此指標進行了一系列的研究并取得了一些好的結(jié)果。其中，樹和單圈圖中具有最大、最小的Wiener極化指數(shù)的極圖已被完全刻畫。
　　對于一般的k值，此問題的研究是困難的。本論文主要是針對給定k值為2和3的點對數(shù)

5、目問題進行研究并得到了一些相應(yīng)的結(jié)果。全文共分為五章。在第一章中，我們介紹了本文所涉及到的基本概念，研究背景以及主要結(jié)果。
　　在第二章中，我們主要對Tyomkyn和Uzzell的一個猜測進行了研究。猜測如下：一個具有n(≥5)個頂點且不含有三個頂點兩兩距離為2的簡單圖的距離為2的點對數(shù)目不超過(n-1)2/4+1。對于頂點數(shù)小于11的情形，他們用計算機驗證了其正確性。而在這一章，我們通過對圖結(jié)構(gòu)的分析得到了一個更一般的結(jié)論：對于

6、一個n(≥5)階且不含有三個頂點兩兩距離為2的簡單圖，如果它含有一個頂點，其鄰域至多被兩個團覆蓋，那么該圖的距離為2的點對的數(shù)目至多為(n-1)2/4+1，并且我們完全刻畫了其極圖。
　　在第三章中，我們主要研究了圖積下的Wiener極化指數(shù)。圖積是圖論中構(gòu)造新圖的重要方法，在網(wǎng)絡(luò)構(gòu)造和設(shè)計中有著重要的應(yīng)用。在這一章，我們研究Wiener極化指數(shù)在四種圖積（卡氏積、強積、直積、字典積）下的變化，并給出了圖積下Wiener極化指數(shù)的

7、關(guān)系式。
　　在第四章中，我們主要研究了雙圈圖的Wiener極化指數(shù)。杜等人給出了對于樹的Wiener極化指數(shù)的一個線性算法并刻畫了具有最大Wiener極化指數(shù)的極圖。隨后一些研究者給出了計算樹、單圈圖的Wiener極化指數(shù)的公式，并且刻畫了給定直徑、最大度條件下的單圈圖中的最大、最小的Wiener極性指標的極圖。在這一章中，我們給出了雙圈圖的Wiener極化指數(shù)的計算公式，并且刻畫了具有最大、最小Wiener極化指數(shù)相應(yīng)的極圖。