Randic指標與圖的若干不變量.pdf

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

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

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

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

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

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

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

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

9、和下界，刻畫了相應的極圖。
　　 在第六章中，我們研究了圖G的反比度I(G)和直徑D(G)的關系，其中反比度的定義為I(G)=0R-1(G)=∑u∈V(G)1/d(u)。Erdos，Pach和Spencer證明，對具有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