關(guān)于Randic指標(biāo)三個問題的解決.pdf

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

2、1975年,由化學(xué)家Randi(c)提出來了Randi(c)指標(biāo)就是其中的杰出代表.圖G的Randi(c)指標(biāo)定義為R=R(G)=∑(d(u)·d(v)-1/2,uv∈E(G)中d(u)表示頂點(diǎn)u的度數(shù).Randi(c)起初用它來描述有機(jī)化合物,特別是碳?xì)浠衔镏刑挤肿庸羌軋D的分支程度.實(shí)際上,化學(xué)家們發(fā)現(xiàn)Randi(c)指標(biāo)與碳?xì)浠衔锢锏闹T如沸點(diǎn)、色譜保留時(shí)間、生成焓、關(guān)于蒸汽壓強(qiáng)的Antoine方程式里的參數(shù)、表面積等物理化學(xué)性質(zhì)

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

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

5、[56],Paxlovi(c)[66],Pavlovi(c),Divni(c)[68]證實(shí)。然而,在2007年,Aouchiche和Hansen利用一個稱為AutoGraphiX的計(jì)算機(jī)系統(tǒng)找到猜想3.1的反例,并且給出一個修正過的猜想(本文記為“猜想3.2”)。在解決最小度δ=n-2以及δ=n-3的情形時(shí),我們發(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ù)學(xué)工作者們十來年的努力,給定頂點(diǎn)數(shù)目n和最小度δ的連通圖中最小Randi(c)指標(biāo)的極值問題終于得到了圓滿的解決。在同一篇文章[18]中,Delorme,Favaron和Rautenbach還“解決了”在給定頂點(diǎn)數(shù)目和最小度δ的不含三角形的圖類中的最小Randi(c)指標(biāo)問題.但是,劉慧清、陸玫、田豐[52]發(fā)現(xiàn)了[18]關(guān)于這個結(jié)論證明中的一個

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