可重圖的Randi?指標的極值問題

胡玉梅(天津大學理學院，天津 300072)

可重圖的Randi?指標的極值問題

胡玉梅
(天津大學理學院，天津 300072)

圖G的Randi?指數，χ(G)，是分子圖的一種拓撲指標，它的值可以反映分子的許多物理化學性質．在化學分子中雙鍵是普遍存在的．為此，研究了恰有一條重邊的可重圖的Randi?指標的極值問題，給出了樹圖及化學樹圖的Randi?指標的極值及相應的結構．

Randi?指標；極值；可重圖；樹圖

一個分子圖的拓撲指標值是由分子的結構圖計算得到的一個數值，它是圖的不變量，一般可以反映分子的物理化學性質和藥物學性質．1975年，Randi?提出了著名的連通性指標(Randi?指標)，因其與分子的物理化學性質，如沸點、表面積等，都有緊密聯系，近年來受到化學家和數學家廣泛關注，詳見參考文獻[1-7]．Randi?指標的定義為χ(G)=其中du和dv分別表示圖G中頂點u和v的度數．

在圖論的應用中，分子的化學結構可以很簡單地表示成圖的形式，這樣的圖也稱為化學圖，或者分子圖．在化學中分子圖中經常遇到多鍵，如甲醛和乙烯等．如果用可重邊來表示多鍵的話，那么就會得到一個可重圖．而目前在研究分子圖的拓撲指標問題的文獻中，多數只研究簡單圖．所以有必要研究在可重圖中拓撲指標的極值問題．

設G(m，n)表示有n個頂點、m條邊的可重圖(存在重邊但沒有環)．如果一個可重圖基本的簡單圖沒有圈，稱為可重樹．稱一個圖為化學圖，其最大度不超過4．簡便起見，筆者稱“恰有一條重邊的可重(化學)樹”為“1-重(化學)樹”．類似的，“1-重路”Pn1表示其基本簡單圖是路的可重樹，且唯一的重邊位于路的一端；“1-重星”Sn1是一個基本簡單圖為星的多重樹．

在分子圖的拓撲指標領域一個很重要的問題就是對于給定圖類的指標的極值以及達到極值時相應圖的結構．早期研究表明在n個頂點的樹中，路圖具有最大的Randi?指標值，而星圖有最小值．Gutman等[8-9]用線性規劃的方法給出了n個頂點的簡單化學樹的最大和最小Randi?指標值．筆者研究恰有一條重邊的n個頂點的可重圖．首先使用線性規劃方法給出了n個頂點的1-重化學樹的最大和最小Randi?指標值．其次，證明了在所有1-重樹中1-重星具有最小的Randi?指標．最后，用Caporossi等[10]的研究方法證明在所有1-重樹中1-重路具有最大的Randi?指標．

1 具有最大和最小Randi?指標的1-重化學樹

在可重圖G(m，n)中，記ni表示i度點的個數；稱一邊為ij邊，如果其端點分別為i度點和j度點，記xij表示ij邊的個數．則有整數線性規劃模型

應用單純形算法，并設m=n．

若取1n、2n、3n、4n、12x、22x為基變量，可得

所有的系數cij都是負值，所以為使χ(G)達到最大值，須有n3和n4的取值盡量?。?/p>

定理1.1 若T是有n個頂點的1-重化學樹，則

證明：假設G*是具有最大Randic指標值的1-重化學樹，即χ(G*)≥χ(Pn1)．因為在1-重化學樹中至少有1個頂點其度大于等于3，則n3+n4≥1．

若在G*中有341nn+＞，則由式(5)和式(6)，得

因為cij＜0，則

與G*的定義矛盾．

若在G*中有n3=0，n4=1，則由式(6)得

證畢．

類似地考慮最小值問題，可以得到下面的定理．證明從略．

定理1.2

(1) 若n≡0(mod3)，則在所有n個頂點1-重化學樹中，沒有2度和3度點(也就是說只有度為1和4的頂點)的樹，記為L1，具有最小的Randi?指標值．

(2) 若n≡1(mod3)，則在所有n個頂點1-重化學樹中，沒有3度點，且只有1個2度點與1個4度點相鄰，二者與唯一的重邊相關聯的樹，記為L2，具有最小的Randi?指標值

(3) 若n≡2(mod3)，則在所有n個頂點1-重化學樹中，沒有2度點，只有1個3度點與2個4度點相鄰，且與唯一的重邊相關聯的樹，記為L3，具有最小的Randi?指標值

2 具有最小Randi?指標值的1-重樹

記T*為n個頂點的具有最小Randi?指標值的1-重樹．稱(dudv)-1/2為邊uv的權重．

引理2.1 設u為T*的一個1度點，v是u的鄰點，則T*中至少存在2條與v相關聯的邊，其權重不超過(2dv)-1/2．

證明：用反證法，假設結論不成立．則T*中v的鄰點，除點s外，都是1度點，且邊sv不是重邊．將邊sv收縮至一點w，且添加一個新的葉子點與w相鄰，得到一個新的1-重樹，記為T′．設xj為除v外s的鄰點，j=1，2，…，ds-1．記ds=x≥2,dv=y ≥2，有

將最后一個等式記為(,)fxy，因為當2x≥、

用歸納法，容易驗證當n=4，5時不等式成立．下面假設n≥6且等式對所有頂點數小于n的1-重樹都成立．

設u為T*的一個1度點，v是u的鄰點，wi(i= 1，2，…，dv-1)是v的除頂點u以外的其他鄰點．顯然有dwi≥1，由引理2.1，有

因為vdn≤，則

由此定理結論成立．證畢．

3 具有最大Randi?指標值的1-重樹

首先區別2種類型的邊：對稱邊和非對稱邊．一條邊稱為對稱邊，如果它的2個端點具有相同的度；否則稱為非對稱邊．

Caporossi[10]等得到簡單圖中Randi?指標的另一種表示形式．不難驗證，這一結果也適用于1-重圖．所以有以下引理．

引理3.1[10]設G為既無孤立點也無環的1-重圖，則Randi?指標可以重新表示為

由上式可見，對稱邊的權重為0，而非對稱邊的權重為正數．

定理 3.2 在所有n個頂點1-重樹中，“1-重路”Pn1具有最大的Randi?指標值．證明：注意到樹圖中必定存在的懸掛邊就是非對稱邊．特別的，在1-重樹中至少存在一個度大于等于3的頂點．為使χ(G)達到最大值，須有非對稱邊的數目盡量少，且非對稱邊的權重盡可能?。绻嬖谀?-重樹恰好同時滿足下列3個條件：

(1) 具有最少的懸掛邊數(=2)；

(2) 在非懸掛邊中，具有最少的非對稱邊數(=1)；

(3) 非對稱邊的權重盡量?。?/p>

則這個樹就具有最大的Randi?指標值．容易驗證，1-重路p1n滿足上述條件的唯一的1-重樹．得證．

4 結 論

(1) 對于n個頂點的1-重化學樹，“1-重路”Pn1具有最大的Randi?指標值；且具有最小的Randi?指標值的1-重化學樹的結構已給出．

(2) 對于n個頂點1-重樹，“1-重星”Sn1具有最小的Randi?指標值；“1-重路”Pn1具有最大的Randi?指標值．

［1］ Li Xueliang，Gutman I. Mathematical Aspects of Randi?-Type Molecular Structure Descriptors，Mathematical Chemistry Monographs No. 1 [M]. Kragujevac：University of Kragujevac and Faculty of Science Kragujevac，2006.

［2］ Li Xueliang，Shi Yongtong．A survey on the Randi? index[J]. MATCH Commun Math Comput Chem，2008，59(1)：127-156.

［3］ Shiu Wai Chee，Zhang Lianzhu．The maximum Randi? index of chemical trees with k pendants [J]. Discrete Mathematics，2009，309(13)：4409-4416.

［4］ You Zhifu，Liu Bolian．On a conjecture of the Randi? index[J]. Discrete Appl Math，2009，157(8)：1766-1772.

［5］ Fischermann M，Hoffmann A，Rautenbach D，et al. A linear programming approach to the generalized Randi? index [J]. Discrete Appl Math，2003，128(2)：375-385.

［6］ Delorme C，Favaron O，Rautenbach D. On the Randi? index [J]. Discrete Math，2002，257(1)：29-38.

［7］ Caporossi G，Gutman I，Hansen P. Variable neighborhood search for extremal graphs IV：Chemical trees with extremal connectivity index [J]. Computers and Chemistry，1999，23(5)：469-477.

［8］ Gutman I，Araujo O，Morales D A. Bounds for the Randi? connectivity index [J]. J Chem Inf Comput Sci，2000，40(3)：593-598.

［9］ Gutman I，Miljkovic O，Alkanes C G，et al. Alkanes with small and large Randi? connectivity indices [J]. Chemical Physics Letters，1999，306(5)：366-372.

［10］ Caporossi G，Gutman I，Hansen P，et al. Graphs with maximum connectivity index [J]. Comput Biol Chem，2003，27(1)：85-90.

Multigraphs with Extremal Randi? Indices

Hu Yumei
(School of Sciences，Tianjin University，Tianjin 300072，China)

χ(G), the Randi? index of G, is a proposed molecular descriptor, and is well correlated with a variety of physico-chemical properties of alkanes. Since multiple bonds are often encountered in molecular graph in chemistry. The purpose of this paper is to derive the extreme values of Randi? index for molecular graph with exactly one multiple bond. The definitions of 1-multitree and chemical 1-multitree are given. Then the extreme values of Randi? index for 1-multitree and chemical 1-multitree are obtained, respectively. And the corresponding structures are also discussed.

Randi? index；extremum；multigraph；tree

O157

A

0493-2137(2013)03-0281-04

2011-05-19；

2011-09-26.

國家自然科學基金資助項目(11001196).

胡玉梅（1977— ），女，博士，副教授．

胡玉梅，huyumei@tju.edu.cn.