Randic指標(biāo)與圖的若干不變量.pdf

1、在歷史上，圖論與化學(xué)有著非常緊密的聯(lián)系?；瘜W(xué)結(jié)構(gòu)可以很簡(jiǎn)單地表示成圖的形式，這樣的圖也稱為化學(xué)圖，或者分子圖。分子的拓?fù)渲笜?biāo)足從化學(xué)圖集合到實(shí)數(shù)集合的一個(gè)映射，理論化學(xué)家和數(shù)學(xué)家提出了眾多的拓?fù)渲笜?biāo)并進(jìn)行研究.本文主要研究一種廣受化學(xué)家和數(shù)學(xué)家關(guān)注的拓?fù)渲笜?biāo)--Randic指標(biāo)，研究Randic指標(biāo)與圖的其它若干不變量之間的關(guān)系，如色數(shù)，半徑，直徑，最小度，最大度，階數(shù)和邊數(shù)，等等.
　　 1975年著名理論化學(xué)家、數(shù)學(xué)化學(xué)家R

2、andic提出了連通性指標(biāo)，即Randic指標(biāo)。(化學(xué))圖G的Randic指標(biāo)定義為R(G)=∑uv∈E(G)(d(u)d(v))-1/2，其中d(u)表示圖G中頂點(diǎn)u的度數(shù)。Randic指標(biāo)與分子的物理化學(xué)性質(zhì)，如沸點(diǎn)、表面積等，都有著緊密的聯(lián)系。1998年，著名數(shù)學(xué)家Bollobas和Erdos將R(G)中的-1/2替換為任意的實(shí)數(shù)α，從而提出了廣義Randic指標(biāo)的定義。理論化學(xué)家和數(shù)學(xué)家對(duì)廣義Rndic指標(biāo)進(jìn)行研究，并且得到了很

3、多重要而深刻的結(jié)果。
　　 第一章是引言部分，介紹了Randic指標(biāo)的定義、研究背景，以及本文中涉及到的相關(guān)概念和基本知識(shí)。以下五章為本文的主要貢獻(xiàn)：
　　 在第二章中，我們指出了Hansen和Melot的文章[Variable neighborhoodsearch for extremal graphs6：Analyzing bounds for the connectivity index，J.Chem.Inf.Co

4、mput.Sci.43(2003)，1-14]中兩個(gè)定理證明的錯(cuò)誤，并給出了正確的證明.這兩個(gè)定理刻畫了化學(xué)樹(shù)的Randic指標(biāo)和葉子點(diǎn)數(shù)之間的聯(lián)系.
　　 在第三章中，我們討論了圖G的Randic指標(biāo)R(G)和最小度δ(G)之間的關(guān)系，并部分解決了Bollobas和Erdos提出的公開(kāi)問(wèn)題。1988年，Shearer證明了如果圖的最小度δ(G)≥1，那么R(G)≥√G≥√n/2，幾個(gè)月后Alon將這個(gè)界改進(jìn)到√n-8。1998

5、年，Bollobas和Erdos證明，如果δ(G)≥1，則有R(G)≥√n-1，其中等號(hào)成立當(dāng)且僅當(dāng)G是星圖。Bollobas和Erdos提出如下問(wèn)題：給定圖G的最小度δ(G)，R(G)的最小值是多少?在2002年，Delorme，F(xiàn)avaron和Rautenbach針對(duì)這一問(wèn)題提出了如下猜想：如果圖G的最小度δ(G)≥k，那么R(G)≥k(n-k)/(√k(n-1)，其中等號(hào)成立當(dāng)且僅當(dāng)圖G是由完全二部圖Kk，n-k做如下變換得到：在

6、Kk，n-k知含有k個(gè)頂點(diǎn)的那部分內(nèi)的任意兩個(gè)頂點(diǎn)連一條邊.提出猜想后，他們證明了k=2時(shí)猜想是成立的。我們驗(yàn)證了k=3時(shí)猜想的正確性，由此很容易地得到猜想中的不等式對(duì)所有的化學(xué)圖也是成立的。更進(jìn)一步，我們證明了當(dāng)k≥4時(shí)，如果圖的頂點(diǎn)數(shù)滿足n≥3/2k3，則猜想是成立的。
　　 在第四章的第一部分，我們完全解決了Caporossi和Hansen提出的關(guān)于圖的Randic指標(biāo)和色數(shù)的猜想：對(duì)頂點(diǎn)數(shù)n≥2的連通圖G，R(G)≥x(

7、G)-2/2+1/√n-1(√X(G)-1+n-X(G))，而且對(duì)所有的n以及2≤X(G)≤n，這個(gè)界是緊的，其中圖G的色數(shù)X(G)是指使得圖G有正常頂點(diǎn)著色(相鄰頂點(diǎn)所著顏色不同)的最小顏色數(shù)目.在第二部分中我們考慮了Fajtlowicz提出的關(guān)于圖的Randic指標(biāo)和半徑的猜想：對(duì)任意連通圖G，R(G)≥r(G)-1，其中圖G的半徑r(G)=minν∈G mayu∈(G)d(u，ν)。根據(jù)Erdos等人的關(guān)于圖的半徑和最小度的結(jié)果，

8、我們證明了若G是具有n個(gè)頂點(diǎn)，最小度為δ(G)的連通圖，如果δ(G)≥n/5且n≥25，則猜想成立；更進(jìn)一步，對(duì)任意實(shí)數(shù)0<ε<1，如果δ(G)≥εn，則對(duì)充分大的n，猜想都是成立的。
　　 在第五章中，我們考慮了具有n個(gè)頂點(diǎn)、m條邊的化學(xué)圖的廣義零階Randic指標(biāo)的極值問(wèn)題，其中廣義零階Randic指標(biāo)定義為0Rα(G)=∑u∈V(G)d(u)α。對(duì)任意的實(shí)數(shù)α，我們用圖的頂點(diǎn)數(shù)和邊數(shù)給出了廣義零階Randic指標(biāo)的嚴(yán)格上界

9、和下界，刻畫了相應(yīng)的極圖。
　　 在第六章中，我們研究了圖G的反比度I(G)和直徑D(G)的關(guān)系，其中反比度的定義為I(G)=0R-1(G)=∑u∈V(G)1/d(u)。Erdos，Pach和Spencer證明，對(duì)具有n個(gè)頂點(diǎn)的連通圖G，若I(G)≥3，則有(2/3[r/3]+o(1)logn/loglogn≤μ(n，r)≤D(n，r)≤(6r+o(1))logn/loglogn，其中μ(G)是圖G的平均距離，μ(n，r)=ma