關于Randic指標三個問題的解決.pdf

1、本文給出了關于圖不變量Randi(c)指標與其它圖不變量,諸如簡單連通圖的最小度、不含三角形簡單圖的最小度、連通簡單圖的圍長的關系的三個猜想的完全證明。上世紀中葉,理論化學家們發(fā)現(xiàn),有機物分子結構的各種不同性質(zhì)的有用信息能夠通過檢驗分子底圖中相關的構造性不變量來獲取。從而,稱那些有化學用途的圖不變量為“拓撲指標”,或者“分子結構指標”.它們主要用來設計并分析所謂的“結構-性質(zhì)定量關系(QSPR,)”和“結構-活性定量關系(QSAR)”.

2、1975年,由化學家Randi(c)提出來了Randi(c)指標就是其中的杰出代表.圖G的Randi(c)指標定義為R=R(G)=∑(d(u)·d(v)-1/2,uv∈E(G)中d(u)表示頂點u的度數(shù).Randi(c)起初用它來描述有機化合物,特別是碳氫化合物中碳分子骨架圖的分支程度.實際上,化學家們發(fā)現(xiàn)Randi(c)指標與碳氫化合物里的諸如沸點、色譜保留時間、生成焓、關于蒸汽壓強的Antoine方程式里的參數(shù)、表面積等物理化學性質(zhì)

3、有很好的相關性.這使得Randi(c)指標被極其廣泛地應用.人們大量地運用分子圖的Randid(c)指標來預測有機化合物的物理化學性質(zhì),特別是藥理性質(zhì)。二十世紀九十年代后半期,著名數(shù)學家Erd(o)s開始從數(shù)學的角度,特別是在某些圖類上Randi(c)指標的極值問題,來研究Randi(c)指標[8,9]。這也引起了許多數(shù)學家對于Randi(c)指標的興趣.Fajtlowitcz提到,Bollobás和Erd(o)s提出了以下極值問題,即

4、:在給定頂點數(shù)目n和最小度δ的連通圖中找出最小Randi(c)指標.特別地,他們在文章[8]中解決了最小度δ=1的情形。
　　 2002年,Delorme,Favaron和Rautenbach[18]解決了當最小度δ=2的極值問題.并且對于一般的最小度δ,他們提出了一個關于此極值問題的猜想(本文記為“猜想3.1”).隨后,猜想3.1關于δ=3、δ=[n/2]、最小度的頂點數(shù)目nδ≥n-δ(δ≤n/2)的情形,分別被李學良,史永堂

5、[56],Paxlovi(c)[66],Pavlovi(c),Divni(c)[68]證實。然而,在2007年,Aouchiche和Hansen利用一個稱為AutoGraphiX的計算機系統(tǒng)找到猜想3.1的反例,并且給出一個修正過的猜想(本文記為“猜想3.2”)。在解決最小度δ=n-2以及δ=n-3的情形時,我們發(fā)現(xiàn)猜想3.2不太精確[45],并將其調(diào)整為猜想3.3.我們將分別在3.2節(jié)和3.3節(jié)中分別給出對于滿足δ≥n/2和δ≤n/2

6、的任意最小度δ猜想3.3正確性的證明。至此,由Bollobás和Erd(o)s提出,經(jīng)過了數(shù)學工作者們十來年的努力,給定頂點數(shù)目n和最小度δ的連通圖中最小Randi(c)指標的極值問題終于得到了圓滿的解決。在同一篇文章[18]中,Delorme,Favaron和Rautenbach還“解決了”在給定頂點數(shù)目和最小度δ的不含三角形的圖類中的最小Randi(c)指標問題.但是,劉慧清、陸玫、田豐[52]發(fā)現(xiàn)了[18]關于這個結論證明中的一個

7、錯誤,從而結論未必正確,并且他們對于最小度δ=2的情形給出了肯定的證明.對于一般的δ,李學良和Gutman在其著作[46]以猜想的形式(本文記為“猜想2.1”)給出.本文將在第二章給出這個猜想的兩種不同形式的證明。在文章[2]中,Aouchiche,Hansen,Zheng給出了關于Randi(c)指標與連通圖圍長之間的關系的一個猜想(本文記為“猜想4.1”).2007年,劉桂真等人[59]證明了對于單圈圖類猜想4.1是正確的.2008