關(guān)于圖的augmented Zagreb指數(shù)和色數(shù)

杜建偉,孫曉玲

(中北大學(xué) 理學(xué)院,山西 太原 030051)

0 引言

拓?fù)渲笖?shù)是從化合物的結(jié)構(gòu)圖衍生出來的不變量,它可以定量描述分子的結(jié)構(gòu),也可以分析相關(guān)分子的結(jié)構(gòu)與性能或活性之間的關(guān)系,在理論化學(xué)、組合化學(xué)和應(yīng)用化學(xué)的研究中都有著廣泛的應(yīng)用[1]。2010年,Furtula等[2]在研究辛烷和庚烷的生成熱時(shí)首次提出了圖G的augmented Zagreb指數(shù)(簡稱為AZI)的定義:

其中d(u)表示圖G中頂點(diǎn)u的度。

本文所考慮的圖G=(V(G),E(G))均為簡單連通圖,其中V(G)是G的頂點(diǎn)集,E(G)是G的邊集。NG(u)(簡寫為N(u))表示G中頂點(diǎn)u的所有鄰點(diǎn)構(gòu)成的集合,dG(u)=|NG(u)|(簡寫為d(u))表示G中頂點(diǎn)u的度。用k種顏色對(duì)圖G的頂點(diǎn)進(jìn)行著色,且沒有相鄰的頂點(diǎn)著相同的顏色,則稱為G的一個(gè)k-頂點(diǎn)著色。k-頂點(diǎn)著色簡稱為k-著色。使圖G為k-著色的k的最小值稱為G的色數(shù),記作χ(G),簡記為χ。Kn表示n個(gè)頂點(diǎn)的完全圖。

設(shè)G和H是點(diǎn)和邊不相交的圖。V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪ {uv|u∈V(G),v∈V(H)},則稱G∨H為G和H的聯(lián)圖。

Gn,l表示滿足|ni-nj|≤1的具有n個(gè)頂點(diǎn)的完全l-部圖,其中ni(i=1,2,…,l)是Gn,l第i部集的頂點(diǎn)數(shù)。

文中未加說明的術(shù)語或記號(hào)可參看文獻(xiàn)[3]。

近年來,augmented Zagreb指數(shù)引起了許多數(shù)學(xué)家、化學(xué)家的關(guān)注, 并發(fā)表了大量理論與應(yīng)用方面的文章。Furtula等[2]得到了化學(xué)樹的augmented Zagreb指數(shù)的上界和下界,并且確定了樹的augmented Zagreb指數(shù)的極小值。Huang等[4]給出了各類連通圖augmented Zagreb指數(shù)的一些上下界,并刻畫了相應(yīng)的極圖。Wang等[5]通過使用不同圖形參數(shù)得到了連通圖的augmented Zagreb指數(shù)的界及相應(yīng)極圖。Du等[6]得到了渺位六角系統(tǒng)augmented Zagreb指數(shù)的上下界及相應(yīng)的極圖,并確定了具有固定懸掛點(diǎn)數(shù)目的化學(xué)樹的augmented Zagreb指數(shù)的最大值。Zhan等[7]給出了單圈圖的極小和第二小augmented Zagreb指數(shù),并且確定了雙圈圖的augmented Zagreb指數(shù)的極小值。更多有關(guān)augmented Zagreb指數(shù)的文章請(qǐng)見文獻(xiàn)[8-16]。本文研究了χ≥2的n階連通圖G的augmented Zagreb指數(shù),當(dāng)n被χ整除時(shí),得到了G的augmented Zagreb指數(shù)的一個(gè)上界,并刻畫了極圖。

1 主要結(jié)果

引理1[4]設(shè)G是階為n≥3的連通圖,且G≠Kn，則

AZI(G)

其中e?E(G)。

定理1 設(shè)G是χ=2的n階連通圖，則

(i)當(dāng)n為奇數(shù)時(shí),

等號(hào)成立當(dāng)且僅當(dāng)G?Gn,2;

(ii)當(dāng)n為偶數(shù)時(shí),

等號(hào)成立當(dāng)且僅當(dāng)G?Gn,2。

AZI(G″)-AZI(G′)=(n1+1)(n2-1)

因此,AZI(G″)>AZI(G′),矛盾。故G′?Gn,2.

證畢。

定理2 設(shè)G是χ≥3的n階連通圖,其中n可以被χ整除,則

AZI(G)≤AZI(Gn,χ),

等號(hào)成立當(dāng)且僅當(dāng)G?Gn,χ。

證明考慮G的一種χ-著色。用ni表示第i種顏色集合中元素的數(shù)目,即ni為著第i種顏色的頂點(diǎn)數(shù),i=1,2,…,χ。

由引理1可知G增加一條邊會(huì)嚴(yán)格增加AZI(G),故

(1)

AZI(G)≤|〈a,b〉|≤‖a‖‖b‖,

(2)

其中‖a‖表示向量a的模。

(2)中|〈a,b〉|=‖a‖‖b‖成立當(dāng)且僅當(dāng)向量a和b線性相關(guān),即a=λb成立,其中λ≠0。因此|〈a,b〉|=‖a‖‖b‖成立當(dāng)且僅當(dāng)對(duì)每一對(duì)i,j(1≤i

nj(n-nk)3(2n-ni-nk-2)3=

nk(n-nj)3(2n-ni-nj-2)3。

(3)

如果nj>nk,那么

(n-nk)3>(n-nj)3,

(2n-ni-nk-2)3>(2n-ni-nj-2)3,

于是

nj(n-nk)3(2n-ni-nk-2)3>

nk(n-nj)3(2n-ni-nj-2)3,

這與(3)矛盾。如果nj

nj(n-nk)3(2n-ni-nk-2)3<

nk(n-nj)3(2n-ni-nj-2)3,

推論1 設(shè)G是χ≥2的n階連通圖,其中n可以被χ整除，則

等號(hào)成立當(dāng)且僅當(dāng)G?Gn,χ。

證明當(dāng)χ=2時(shí),由定理1中(ii)的結(jié)果,可知推論成立。

由(2),有