單圈圖的遺忘指數(shù)的上界

周后卿，姚志雄

(1.邵陽(yáng)學(xué)院 理學(xué)院，湖南 邵陽(yáng)，422000；2.邵陽(yáng)市第一中學(xué)，湖南 邵陽(yáng)，422000)

20世紀(jì)70年代，GUTMAN和TRINAJSTIC[1]導(dǎo)出了計(jì)算總π-電子能量的近似公式。這些公式中有一項(xiàng)，就是分子圖的頂點(diǎn)度的平方和，這個(gè)量被認(rèn)為是對(duì)底層分子的碳原子骨架的分支程度的度量。后來(lái)被稱作第一類Zagreb指數(shù)，成為了一個(gè)最廣泛的基于圖的分子結(jié)構(gòu)描述符之一的量的研究。文獻(xiàn)[1]中的能量計(jì)算公式同樣用到了一個(gè)量，就是頂點(diǎn)的度的立方和(記作F)，它也是分支的一個(gè)度量。但這個(gè)量沒(méi)有被引起注意，以致后來(lái)這個(gè)量被忘記，所以被稱作遺忘的拓?fù)渲笖?shù)。關(guān)于這個(gè)拓?fù)渲笖?shù)的研究文獻(xiàn)不多，文獻(xiàn)[2]研究了分子圖的遺忘指數(shù)的一些性質(zhì)，它與第一類Zagreb指數(shù)相結(jié)合，具有較大的應(yīng)用潛力。辛烷值包括沸點(diǎn)、熔點(diǎn)、熱容、熵、密度、蒸發(fā)熱、生成焓、馬達(dá)法辛烷值、摩爾折射率、偏心系數(shù)、總表面積、辛醇-水分配系數(shù)、摩爾體積。F指數(shù)與上述各項(xiàng)性質(zhì)相關(guān)。與第一類Zagreb指數(shù)的結(jié)果進(jìn)行比較，F(xiàn)指數(shù)的預(yù)測(cè)能力與第一類Zagreb指數(shù)的預(yù)測(cè)能力相似，從而看出F指數(shù)也是一個(gè)比較有用的分子描述符。

定義分子圖的遺忘指數(shù)F為

通過(guò)計(jì)算各種化合物和藥物分子結(jié)構(gòu)的遺忘拓?fù)渲笖?shù)，預(yù)測(cè)新化合物和藥物的生物學(xué)特性，在醫(yī)藥領(lǐng)域具有重要意義。目前關(guān)于F指數(shù)的研究文獻(xiàn)不多，文獻(xiàn)[8]測(cè)定了聚丙醚亞胺、卟啉和鋅卟啉樹(shù)枝狀大分子的遺忘拓?fù)渲笖?shù)。文獻(xiàn)[9-15]研究了基于圖的運(yùn)算所得到的聯(lián)圖等的遺忘拓?fù)渲笖?shù)。本文研究基于單圈圖的卡氏積圖的F指數(shù)的界的問(wèn)題。

1 基本概念和基本性質(zhì)

首先介紹幾個(gè)基本的定義與公式。

先介紹幾個(gè)基本概念及性質(zhì)。

設(shè)f(x)在區(qū)間I上有定義，若對(duì)于任意x1，x2∈I和t∈(0，1)，有f(tx1+(1-t)x2)≤tf(x1)+(1-t)f(x2)，則稱f(x)在區(qū)間I上是下凸的；若f(tx1+(1-t)x2)≥tf(x1)+(1-t)f(x2)，則稱f(x)在區(qū)間I上是上凸的。

單圈圖是指圖的頂點(diǎn)數(shù)與邊數(shù)相等的連通圖；正則圖是指圖中每個(gè)頂點(diǎn)的度都相等的圖；圈圖是指每個(gè)頂點(diǎn)度為2的連通圖。

再看笛卡爾積(簡(jiǎn)稱為卡氏積)圖的定義，兩個(gè)連通圖G和H的卡氏積G×H是一個(gè)連通圖，它的頂點(diǎn)數(shù)就是G與H的頂點(diǎn)數(shù)的積，即|V(G×H)|=|V(G)|×|V(H)|。

考慮集合

A={((u，v1)，(u，v2))|u∈V(G)且(v1，v2)∈E(H)}

和B={((u1，v)，(u2，v))|(u1，u2)∈E(G)且v∈V(H)}，

卡氏積G×H的邊集為E(G×H)=A∪B。從而可推出G×H的邊數(shù)為

|E(G×H)|=|E(G)|·|V(H)|+|V(G)|·|E(H)|。

對(duì)于卡氏積G×H圖的最大度，有Δ(G×H)=Δ(G)+Δ(H)。

對(duì)于M1和M2，有以下結(jié)論。

結(jié)論3[17]設(shè)G是一個(gè)具有頂點(diǎn)n、邊m、最小度δ的連通圖，則

等式成立當(dāng)且僅當(dāng)G是星圖或完全圖。

2 引理與定理

本文主要研究單圈圖以及幾類卡氏積圖的遺忘指數(shù)問(wèn)題。

首先給出下列引理。

還需證明下列引理。

引理2設(shè)di>0(i=1，2，…，n)，n∈Ν*，當(dāng)λ>1時(shí)，下列不等式成立：

證明令f(x)=xλ，因?yàn)閒′(x)=λxλ-1，f″(x)=λ(λ-1)xλ-2，當(dāng)x>0，λ>1時(shí)，有f″(x)>0，所以，函數(shù)f(x)=xλ為向下凸。

現(xiàn)在給出單圈圖的遺忘指數(shù)的界。

定理1設(shè)圖Un是具有頂點(diǎn)n的單圈圖，則其遺忘指數(shù)滿足不等式8n≤F≤2n3，左邊等式成立當(dāng)且僅當(dāng)Un同構(gòu)Cn，這里，Cn為圈圖。

接下來(lái)，研究單圈圖Gn與單圈圖Hm的卡氏積Gn×Hm的遺忘指數(shù)的界的問(wèn)題。給出下列3個(gè)圖，圖1是具有5個(gè)頂點(diǎn)的單圈圖，圖2是1個(gè)3圈圖，它們的笛卡爾積圖如圖3所示。

圖1 具有5個(gè)頂點(diǎn)的單圈圖U5Fig.1 Unicyclic graph U5 with 5 vertices

圖2 3圈圖C3Fig.2 Tricyclic graphs C3

圖3 具有15個(gè)頂點(diǎn)的卡氏積圖U5×C3Fig.3 Cartesian product with 15 vertices U5×C3

定理3 設(shè)具有n個(gè)頂點(diǎn)單圈圖Gn與具有m個(gè)頂點(diǎn)的單圈圖Hm的笛卡爾積為Gn×Hm，則Gn×Hm的遺忘指數(shù)滿足不等式F≤16(mn)3。

證明不妨設(shè)Gn的頂點(diǎn)集為V(Gn)={1，2，…，n}，Hm的頂點(diǎn)集為V(Hm)={v1，v2，…，vm}，那么Gn×Hm包含有mn個(gè)頂點(diǎn)，它的頂點(diǎn)度之和可以表示成

由引理2有

因?yàn)镚n×Hm包含有mn個(gè)頂點(diǎn)，它的頂點(diǎn)度之和可以表示成

所以，根據(jù)引理2得